UVa 104

From Algorithmist

Contents 1 104 - Arbitrage 2 Summary 3 Explanation 4 Gotchas 5 Input 6 Output

[edit] 104 - Arbitrage

• http://online-judge.uva.es/p/v1/104.html

[edit] Summary

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

[edit] Explanation

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 O(N³) 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 ( 1 < = n < = 20 ).

Modifications to be done to Floyd-Warshall algorithm:

[edit] Gotchas

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 is valid.

[edit] Input

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

[edit] Output

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