104  Arbitrage
Moderator: Board moderators
Who can send the source of this problem(104) to me?
Thanks!!
myemail: hankii@ms10.url.com.tw
Thanks!!!
Thanks!!
myemail: hankii@ms10.url.com.tw
Thanks!!!
Hey, for some code to this, go to http://www.pi.informatik.tudarmstadt.d ... eme/1/104/ It's not in English but there's like three DIFFERENT solutions there, in C code!!!
well, this question has got to do with searching for negative cycles in a graph. represent each currency by a vertex in a graph, with the edge weights the negative of the log of the currency exchange value. If a negative cycle can be found, then a arbitrage cycle exists. The length of the negative cycle is the length of the arbitrage cycle.

 New poster
 Posts: 2
 Joined: Sun Mar 17, 2002 2:00 am
I tried to solve the same problem but i got WA and i don't know why. The solutions seem to be correct... Here is the source in Pascal, maybe someone can tell me what's wrong... My email is vlad_ionescu@rdslink.ro. Thx.
program arbitrage(input, output);
var m:array[1..20,1..20] of real;
v:array[1..20,1..20] of 1..20;
sol:array[1..21] of 1..20;
n,i,j,k,p,l,t:integer;
mk:set of byte;
d:boolean;
procedure royfloyd;
var k,i,j:integer;
b:boolean;
begin
b:=false;
for k:=1 to n do begin
for i:=1 to n do begin
for j:=1 to n do
if (v[i,j]+v[i,k]<=n) and (m[i,k]*m[k,j]>m[i,j]) and (m[i,j]<=1.01) then begin
m[i,j]:=m[i,k]*m[k,j];
if (i=j) and (m[i,j]>1.01) then begin
b:=true; p:=i;
end;
v[i,j]:=v[i,k]+v[k,j];
if b then break;
end;
if b then break;
end;
if b then break;
end;
end;
procedure afis(s,f:integer);
var b:boolean;
begin
b:=false;
for k:=1 to n do
if not (k in mk) and (k<>s) and (k<>f) and (m[s,k]*m[k,f]=m[s,f]) and (m[s,k]<>1) and (m[k,f]<>1) then begin
mk:=mk+[k];
b:=true;
afis(s,k); afis(k,f);
break;
end;
if not b then begin
t:=t+1;
sol[t]:=f;
end;
end;
begin
while not eof(input) do begin
readln(n);
for i:=1 to n do begin
for j:=1 to n do begin
if i<>j then read(input,m[i,j])
else m[i,j]:=1;
v[i,j]:=1;
end;
readln(input);
end;
p:=0;
royfloyd;
mk:=[];
if p<>0 then begin
sol[1]:=p;
t:=1;
afis(p,p);
repeat
d:=true;
for i:=1 to t1 do if sol>sol[i+1] then begin
d:=false;
l:=sol;
sol:=sol[i+1];
sol[i+1]:=l;
end;
until d;
for i:=2 to t do
if sol=sol[i1] then begin
for j:=i to t do sol[j1]:=sol[j];
break;
end;
sol[t]:=sol[1];
for i:=1 to t do write(output,sol:1,' ');
end
else write(output,'no arbitrage sequence exists');
writeln(output);
end;
end.
<font size=1>[ This Message was edited by: vlad ionescu on 20020317 17:20 ]</font>
program arbitrage(input, output);
var m:array[1..20,1..20] of real;
v:array[1..20,1..20] of 1..20;
sol:array[1..21] of 1..20;
n,i,j,k,p,l,t:integer;
mk:set of byte;
d:boolean;
procedure royfloyd;
var k,i,j:integer;
b:boolean;
begin
b:=false;
for k:=1 to n do begin
for i:=1 to n do begin
for j:=1 to n do
if (v[i,j]+v[i,k]<=n) and (m[i,k]*m[k,j]>m[i,j]) and (m[i,j]<=1.01) then begin
m[i,j]:=m[i,k]*m[k,j];
if (i=j) and (m[i,j]>1.01) then begin
b:=true; p:=i;
end;
v[i,j]:=v[i,k]+v[k,j];
if b then break;
end;
if b then break;
end;
if b then break;
end;
end;
procedure afis(s,f:integer);
var b:boolean;
begin
b:=false;
for k:=1 to n do
if not (k in mk) and (k<>s) and (k<>f) and (m[s,k]*m[k,f]=m[s,f]) and (m[s,k]<>1) and (m[k,f]<>1) then begin
mk:=mk+[k];
b:=true;
afis(s,k); afis(k,f);
break;
end;
if not b then begin
t:=t+1;
sol[t]:=f;
end;
end;
begin
while not eof(input) do begin
readln(n);
for i:=1 to n do begin
for j:=1 to n do begin
if i<>j then read(input,m[i,j])
else m[i,j]:=1;
v[i,j]:=1;
end;
readln(input);
end;
p:=0;
royfloyd;
mk:=[];
if p<>0 then begin
sol[1]:=p;
t:=1;
afis(p,p);
repeat
d:=true;
for i:=1 to t1 do if sol>sol[i+1] then begin
d:=false;
l:=sol;
sol:=sol[i+1];
sol[i+1]:=l;
end;
until d;
for i:=2 to t do
if sol=sol[i1] then begin
for j:=i to t do sol[j1]:=sol[j];
break;
end;
sol[t]:=sol[1];
for i:=1 to t do write(output,sol:1,' ');
end
else write(output,'no arbitrage sequence exists');
writeln(output);
end;
end.
<font size=1>[ This Message was edited by: vlad ionescu on 20020317 17:20 ]</font>
It shouldn't be preferred in any way, though it will be the first to pop up if you solve it in certain way. If I'm not mistaken, then if there are sequences of the same length, sequence with the best result should be chosen. Or maybe not... The problem doesn't state it, but my algorithm worked fine that way.
Ivor
Ivor
thanx for the reply,
I used a modification Depth First Search. I got "1 2 3 1" as the answer if I consider first profit sequence. And I get "2 4 3 2" if I consider the best profit sequence. Thats was why I was not sure about my understanding.
<font size=1>[ This Message was edited by: ram on 20020324 01:04 ]</font>
I used a modification Depth First Search. I got "1 2 3 1" as the answer if I consider first profit sequence. And I get "2 4 3 2" if I consider the best profit sequence. Thats was why I was not sure about my understanding.
<font size=1>[ This Message was edited by: ram on 20020324 01:04 ]</font>
watch out for multiple cycles
I am not sure what is wrong with your code. But did you handle the case in which the solution is a multiple cycle ?
for example:
for N = 10
1  2  3  1  2  3  1 , or something similiar.
In addition, you need to find a sequence of length <= N, and the minimum length sequence in case of a tie.
for example:
for N = 10
1  2  3  1  2  3  1 , or something similiar.
In addition, you need to find a sequence of length <= N, and the minimum length sequence in case of a tie.
Hieu Nguyen