## 104 - Arbitrage

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
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
I stay home. Don't call me out.

globi
New poster
Posts: 15
Joined: Wed Apr 23, 2003 2:44 pm
Location: Warsaw
Contact:

### 104 - "Arbitrage" - plz help

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
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
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
I stay home. Don't call me out.

globi
New poster
Posts: 15
Joined: Wed Apr 23, 2003 2:44 pm
Location: Warsaw
Contact:

### Tip: Styles can be applied quickly to selected text.

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

Larry
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 Bellman-Ford).

Feng
New poster
Posts: 3
Joined: Sat May 28, 2005 8:11 am

### shortest or longest path?

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
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am
It is not to maximise profit. It is to find the shortest path that is profitable.

stautxie
New poster
Posts: 1
Joined: Sat Jun 11, 2005 3:04 am
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
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[ 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
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am
Thanks alot for your hints

Hardi
New poster
Posts: 12
Joined: Fri Jun 10, 2005 2:44 pm
Location: Estonia, P
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?
"There is no point in learning facts, which are derived from logic, if you can learn the logic to derive facts" - Hardi Pertel

dhyanesh
New poster
Posts: 5
Joined: Sat Feb 26, 2005 5:28 am
Yups that is right

Hardi
New poster
Posts: 12
Joined: Fri Jun 10, 2005 2:44 pm
Location: Estonia, P

### 104

Hy.
Please explain me, how does Floyd-Warshall 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

Mohammad Mahmudur Rahman
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.
You should never take more than you give in the circle of life.

Hardi
New poster
Posts: 12
Joined: Fri Jun 10, 2005 2:44 pm
Location: Estonia, P
No it doesn't. Explain me the Floyd-Warshall algorithm
I don't know anything about O(n^3) or O(n^2) etc...
"There is no point in learning facts, which are derived from logic, if you can learn the logic to derive facts" - Hardi Pertel