#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 PHPGraphLib - Click For Official Site