104  Arbitrage
Moderator: Board moderators
104  "Arbitrage"  plz help
Could anybody tell me, how should I modify FloydWarshall algo O(n^3), to receive correct answer?
I know how to solve same problem (using FW) 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) FW
3) I look at diagonal of d[][] to see if te value exceed 1.01
Is it correct, and what now ?
Thanks for help
I know how to solve same problem (using FW) 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) FW
3) I look at diagonal of d[][] to see if te value exceed 1.01
Is it correct, and what now ?
Thanks for help
Sorry, I don't know the O(n^3) algorithm. But I know this of O(n^4). I hope this helps.
http://onlinejudge.uva.es/board/viewto ... 0923#30923
http://onlinejudge.uva.es/board/viewto ... 0923#30923
I stay home. Don't call me out.
Tip: Styles can be applied quickly to selected text.
Thanks, but I'm still looking for O(n^3) solution .

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
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 BellmanFord).
Check out http://www.algorithmist.com !
shortest or longest path?
I still don't understand why FW algorithm can be used here  to maximize the profit it sounds like a longest path problem.
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)
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)

 New poster
 Posts: 28
 Joined: Mon Nov 04, 2002 8:03 pm
 Location: South Korea, Seoul
 Contact:
use the O(n^4) my code..
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[ step1 ][ from ][ mid ] * data[ mid ][ to ] ) ....
( above code is almost same 'FloydWarshall' 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
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.178331.00 $ ???
Is it really true or am I miscalculating something?
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.178331.00 $ ???
Is it really true or am I miscalculating something?
"There is no point in learning facts, which are derived from logic, if you can learn the logic to derive facts"  Hardi Pertel
104
Hy.
Please explain me, how does FloydWarshall algorithm work and how can I use it to solve the Arbitrage problem.
Please explain me, how does FloydWarshall algorithm work and how can I use it to solve the Arbitrage problem.
"There is no point in learning facts, which are derived from logic, if you can learn the logic to derive facts"  Hardi Pertel

 Experienced poster
 Posts: 154
 Joined: Sat Apr 17, 2004 9:34 am
 Location: EEE, BUET
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.
AFAIK there is a better O(n^3) algorithm for this problem but I could not figure that out.
Hope it helps.
You should never take more than you give in the circle of life.