# UVa 104

## 104 - Arbitrage[edit]

## Summary[edit]

This problem can be categorized as a Dynamic Programming or Graph Theory problem. Any algorithm will get you an AC.

## Explanation[edit]

This problem requires knowledge of graph algorithms and can be solved using modified version of Floyd-Warshall algorithm. Floyd-Warshall algorithm will find all the shortest paths between every node to the others in just time. Remember, finding the shortest path from every node to others won't suffice, as we need to select path with least number of exchanges involved. So, add another dimension to the distance matrix, which will store the optimal path in 'n' no. of steps ( ).

Modifications to be done to Floyd-Warshall algorithm:

## Gotchas[edit]

You have to find the shortest sequence that yields a profit and **not** the one with the greatest profit! If there is more than one sequence with the same length, any of those are valid.

## Input[edit]

3 1.2 .89 .88 5.1 1.1 0.15 4 3.1 0.0023 0.35 0.21 0.00353 8.13 200 180.559 10.339 2.11 0.089 0.06111 2 2.0 0.45 6 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.1 0.0 0.0 0.0 0.0 1.0 0.0 0.0 0.0 5.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 9.0 0.0 0.0 0.0 0.0 1.0

## Output[edit]

1 2 1 1 2 4 1 no arbitrage sequence exists 5 6 5