#104 - Arbitrage| Solved By: | wesley | | Theory Difficulty: | easy | | Coding Difficulty: | easy | | Algorithms Used: | dynamic programming
floyd warshall
| | Solution Description: | If the problem was to find the most profitable path, then it would be very simple to use Floyd-Warshall, but with the updating line:
a[i][j] = Math.max(a[i][j], a[i][k]*a[k][j])
...but, we need to find the shortest path that yields a 1% profit. I'd recommend using an O(n^4) all-pairs shortest-path algorithm that updates based on path length. Of course, we'll use it for maximum product rather than shortest length. For instace:
a[i][j][s] is the maximum product from i to j in s steps.
for s from 2 to n
for i from 1 to n
for j from 1 to n
for k from 1 to n
--- a[i][j][s] = max(a[i][j][s], a[i][j][s-1]*a[j][k][1])
At the end, find the smallest s (and any i) such that a[i][i][s] > 1.01 |
Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By 
|