[ACM] Some hints about uva 104 (Modified Floyd-Warshall)

by gits
Original Thread http://online-judge.uva.es/board/viewtopic.php?t=7292

Well, I'll assume you understand what the problem asks. You have to find the shortest sequence that yelds a profit (not the one with the greatest profit!). If there is more then one sequence with the same length, any of those is valid.

Now, you can't just try with brute force (trying all combinations) because it'll be too slow and you'll get Time Limit Exceeded. However, there's a well known algorithm, Floyd-Warshall, which will find all the shortest paths between every node to the others in just O(n^3) time. You can find more info about F-W in the net. In my previous post I said how you have to change the general F-W algorithm to work for this particular problem...

As for floating point errors, most numbers representation isn't totally acurate; for instance, 0.1 is usually stored as 0.10000000000000001. After some operations, the error may influence the final result. Again, search the net for floating point errors. However, you won't have to deal with these errors to solve this problems (at least I didn't).

Hope this helps


=================================
Floyd-Warshall finds all the mininum paths between every vertex and all the other vertexes. However, in this problem you not only have to find the shortest path, it also has to make a profit of more than 1%.

Simple F-W goes like this:

// initialization
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      best[i][j] = path[i][j];
      path[i][j] = i;
    }
}

for (k = 0; k < n; k++) {
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (best[i][k] + best[k][j] < best[i][j]) {
                best[i][j] = best[i][k] + best[k][j];
                path[i][j] = k;
            }
        }
   }
}

For this problem, instead of having best[i][j] and path[i][j] I have best[i][j][s] and path[i][j][s], which means "best path from i to j in s steps". I also have an outer loop, representing the number of steps.

// initialization
best[i][j][s] = 0, for all i,j,s
best[i][j][1] = input for the program
best[i][i][1] = 1, for all i
path[i][j][1] = i, for all i, j

for (steps = 2; steps <= n; steps++)
    for k...
        for i..
            for j..
                tmp = best[i][k][steps-1] * best[k][j][1]
                if (tmp > best[i][j][steps]) {
                    best[i][j][steps] = tmp;
                    path[i][j][steps] = k;
                }

What we are doing is to find the most profitable way to go from i to j in "steps" steps, trying for each to use k as the point just before j. As you can see, this is O(n^4) but since max n is 20 it's ok.

After this, you scan though best[i][i][s] (best way to go from i to i again, in s steps). Remember that you want the minimum number of steps that yields a profit; so it's this:

for (steps = 2; steps <= n; steps++)
    for (i = 0; i < n; i++)
        if (best[i][i][steps] > 1.01) {
            // score!
        }

If the "if" never matches, then there is no arbitrage sequence. If it matches, you have to print the path. To print the path, use path[i][i][steps], which is the vertex just before the last (i).

For instance, if i is 1 and steps is 4. Check path[1][1][4]. Suppose it is 2. So the path ends with "... 2 1". Now check path[1][2][3]. Supposing it's 4, the path ends with "... 4 2 1". Now check path[1][4][2]. If it's 5, the path is "... 5 4 2 1". Finally check path[1][5][1], which will be obviously 1. So the complete path is "1 5 4 2 1" (exactly 4 steps).

Just remember that path[i][j][s] is the vertex which is before the last one in a path from i to j in s steps. If s is 1, the path is simply "i j". In this problem you have to start and finish in the same currency; that's why we only search in best[i][i][steps].

Hope this helps, I almost wrote the complete program!

You could also stop the algorithm as soon as you found a solution. In other posts, some people talked about a O(n^3) solution but I can't figure it out... if someone has such a solution please mail it to me, I would love to learn how to do this in a better way.

Good luck and happy coding!