## Wednesday, August 6, 2014

### a bit of uva: UVa 104 - Arbitrage

Problem Statement:
UVa 104 - Arbitrage

Summary:
Given an adjacency matrix, find the shortest cycle such that the product of the edges is bigger than 1.01

I was stuck on this problem for a while (I sincerely think that this question is difficult! haha) because a lot of people said they solved this problem simply by running Floyd-Warshall on the graph. However, I really don't think that the implementation is that obvious. Eventually, I learnt a way to solve the problem, it resembles Floyd-Warshall, but not exactly the same. It borrows the main idea that we can incrementally build an optimal path by considering k = 1,2,...,N one by one.

The idea is this:
Suppose we are given a path with $$m$$ edges for each pair of vertices $$(i,j)$$such that the product of the edges is maximum (in other words, the optimal path using $$m$$ edges). Then to find the optimal path between $$i,j$$ using $$m+1$$ edges can be done by trying all $$k = 1,2,3,\ldots, N$$ and choose $$k$$ such that the path i-k-j (where i-k has $$m$$ edges, k-j is a direct edge\) is optimal. That means, we take D[i][j][m+1] = max of ( D[i][k][m] * D[k][j] ) for k = 1,2,...,N. Now it remains to prove that the path we found is indeed optimal, and the proof is by contradiction. Suppose that there is $$p$$ = i-k'-j (where i-k' has m edges, k'-j is a direct edge) with $$k' \neq k$$ such that the product of its edges are larger than that of i-k-j. Furthermore, suppose that $$q$$ is the path i-k'-j such that i-k' is the optimal path using m edges. Then we have: product of edges of $$p$$ $$\leq$$ product of edges of $$q$$ < product of edges of i-k-j, contradiction. Therefore i-k-j found must have been optimal.

As such we can solve the problem by iterating through m starting from m = 2, with the initial condition of m=1 which is the initial adjacency matrix. We also need to maintain a path matrix to reconstruct the path found. This is done by storing the information about the parent of j in a path between i and j: At first, every parent of j is i for all i-j. During the progress of the algorithm, if i-k-j is larger than i-j, update par[i][j] = k (since the parent of j is now k).

Implementation:

void floyd(){
for(int s=1;s<N;++s) //0 indexed
for(int k=0;k<N;++k)
for(int i=0;i<N;++i)
for(int j=0;j<N;++j){
double temp = arb[i][k][s-1]*arb[k][j];
if(temp > arb[i][j][s]){
arb[i][j][s] = temp;
par[i][j][s] = k; //since par[k][j] = k
}
}
}