Codeforces Round #356 (Div. 1) - D. Bear and Chase

Problem Statement:
Codeforces Round #356 (Div. 1) - D. Bear and Chase

Summary:
We are to maximise the probability of guessing the position of a target in an undirected graph, given that the procedure that we must follow is:
Step 1. Choose a node. The shortest distance to the target is revealed. We either guess where the target is, or go to step 2.
Step 2. Target moves to another node via an edge. Now choose a node again and the shortest distance to the target is revealed. Guess where the target is.
Initially each node has equal probability of containing the target. After Step 1, target moves to a neighbouring node with equal probability among the neighbours.

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][1] ) 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][0];
               if(temp > arb[i][j][s]){
                  arb[i][j][s] = temp;
                  par[i][j][s] = k; //since par[k][j][0] = k
               }
            }
}