104 - Arbitrage

[ImLazy]

Dear gits, I know you are a good friend. So can you help me to understand the 114?
http://online-judge.uva.es/board/viewtopic.php?t=7311

[globi]

Could anybody tell me, how should I modify Floyd-Warshall algo O(n^3), to receive correct answer?

I know how to solve same problem (using F-W) but without limit to number of exchanges and this great 1% ;].

What I already know:
1) I change the d[j] = min(d[j], d[k] + d[k][j]) to d[j] = max(d[j], d[k] * d[k][j])
2) F-W
3) I look at diagonal of d[][] to see if te value exceed 1.01

Is it correct, and what now ?

Thanks for help

[ImLazy]

Sorry, I don't know the O(n^3) algorithm. But I know this of O(n^4). I hope this helps.
http://online-judge.uva.es/board/viewto ... 0923#30923

[globi]

Thanks, but I'm still looking for O(n^3) solution .

[Larry]

I don't know how to solve this particular one in O(n^3), but you can model arbitrages as a graph based on the logarithm of the multiplier, and then try to find a negative cycle using Floyd Warshall (or Bellman-Ford).

[Feng]

I still don't understand why F-W algorithm can be used here - to maximize the profit it sounds like a longest path problem.

[roticv]

It is not to maximise profit. It is to find the shortest path that is profitable.

[stautxie]

I have a DP algorithm that tailors FW algorithm:

H(i,j) denotes the max asset among any sequence in the type of (i, ..., j, i)
prev(i,j) denotes the index just before j

I use a loop to denote the length of arbitrage,

for(int l = 2; l < n; ++l ) {
if (l == 2)
{
//use definition (i,j,i)
if any H(i,j) > 1.01 // escape
}
else {
H(i,j) = max ( H(i,j), H(i,k) / convert(k,i) * convert(k,j) * convert(j,i);
prev(i,j) = k;
if any H(i,j) > 1.01 // escape
}
}

using this trick, I only need O(N^2) storage rather than O(N^3)

[Gaolious]

Code: Select all

for step = 1 ~ n 
begin

  for from = 0 ~ n
  for to = 0 ~ n
  for mid = 0 ~ n
   if  DP[ step ][ from ][ to ] < DP[ step-1 ][ from ][ mid ] * data[ mid ][ to ] ) ....
   ( above code is almost same 'Floyd-Warshall' algorithm )
  
  if exist the "maximum profit" with "more than 1.01" in "this step"
    exit loop
end

print profit and path, if profit is more than 1.01, else print "no arbitrage sequence exists";

and, the 'step' use for print path

[roticv]

Thanks alot for your hints

[Hardi]

I think something is wrong:

Sample Input

3
1.2 .89
.88 5.1
1.1 0.15
4
3.1 0.0023 0.35
0.21 0.00353 8.13
200 180.559 10.339
2.11 0.089 0.06111
2
2.0
0.45

Sample Output

1 2 1
1 2 4 1
no arbitrage sequence exists

In the 2th input:

The table:
| 1 | 2 | 3 | 4
-------------------------------------------
1 | x | 3.1 | 0.0023 | 0.35
-------------------------------------------
2 | 0.21 | x | 0.00353 | 8.31
-------------------------------------------
3 | 200 | 180.559| x | 10.339
-------------------------------------------
4 | 2.11 | 0.089 | 0.06111 | x
-------------------------------------------
when I convert 1 to 2 then I get 3,1;
when I convert 2 to 4 I'll get 3.1 * 8.13 = 25.203
when I convert 4 to 1 I'll get 25.203 * 2.11 = 53.17833

So the arbitrage trader will earn 53.17833-1.00 $ ???

Is it really true or am I miscalculating something?

[dhyanesh]

Yups that is right

[Hardi]

Hy.
Please explain me, how does Floyd-Warshall algorithm work and how can I use it to solve the Arbitrage problem.

[Mohammad Mahmudur Rahman]

I used a O(n^4) algorithm with a 3D array. I nested the entire Floyd warshall inside a loop (for s= 2 to n) & tried to find the maximum profit from i to j for some (i,j) using at most s transactions. The loop terminated when a profitable path is found.
AFAIK there is a better O(n^3) algorithm for this problem but I could not figure that out.
Hope it helps.

[Hardi]

No it doesn't. Explain me the Floyd-Warshall algorithm
I don't know anything about O(n^3) or O(n^2) etc...