Uva 104 - Arbitrage

Problem: Uva 104 - Arbitragedownload

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 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:

[Source: http://www.algorithmist.com/index.php/UVa_104, 26/09/2015]


Details:

This problem can be solved by using all shortest path (graph) algorithm. We can use Floyd-Warshall algorithm. This algorithm cannot be use directly. At first, I would like to describe flayd-Warshall Algorithm:

Simple F-W goes like this: 
More specific: k + k-->j is smaller than the original i-->j */ if (d[i][k] + d[k][j] < d[i][j]) { /* then reduce i-->j distance to the smaller one i->k->j */ d[i][j] = d[i][k]+d[k][j]; /* and update the predecessor matrix */ p[i][j] = p[k][j]; } ]]>

--> -->

There are two matrix, one represent parent path (path matrix) & other represent profit/weight matrix.

NOW WE discuss about given problem, we have to modify this algorithm:

TICS:

1.       We have to modify the Floyd –warshall  algorithm : i.e

                       Profit_ij=max( profit_ij, profit _ik*profit_kj)

2.       We have to store the path not only one node-àintermediate node -àother node. But also other path like 1-->2-->3-->.So we need three dimension array or we can use structure or other which give you more profit.

3.       We only check diagonal element of calculated matrix i.e (1,1),(2,2)

Now check [0][0] and [1][1] element for each step. If the value of that element is greater than 1.01 , then stop the checking loop. If Anyone can not satisfy the given condition then , print “no arbitrage sequence exists”

If found then only print the path value of that element (I,j) of each step…..

Code:

-----------