OJ Board

Posted: **Thu Jan 20, 2005 5:59 am**

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

Posted: **Fri Feb 11, 2005 9:42 pm**

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

Posted: **Tue Feb 15, 2005 12:52 pm**

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

Posted: **Wed Feb 16, 2005 12:44 am**

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

.

Posted: **Wed Feb 16, 2005 3:16 am**

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).

Posted: **Sat May 28, 2005 8:26 am**

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

Posted: **Fri Jun 03, 2005 5:00 am**

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

Posted: **Sat Jun 11, 2005 3:12 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)

Posted: **Sat Jun 11, 2005 7:38 am**

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

Posted: **Sun Jun 12, 2005 6:49 am**

Thanks alot for your hints

Posted: **Mon Jun 13, 2005 7:19 pm**

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?

Posted: **Mon Jun 13, 2005 10:55 pm**

Yups that is right

Posted: **Tue Jun 14, 2005 12:00 pm**

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

Posted: **Tue Jun 14, 2005 9:33 pm**

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.

Posted: **Thu Jun 16, 2005 2:41 pm**

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

OJ Board

104 - Arbitrage

104 - "Arbitrage" - plz help

Tip: Styles can be applied quickly to selected text.

shortest or longest path?

use the O(n^4) my code..

104