## 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

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
took another glance at your code, seems you have nowhere stating something like "1.01". only >1.01 will be printed, i remember it's stated somewhere in the problem.

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
no...
you can look more carefully,i first set the start point to "1",and then start transfering,and if something transfer into the start point and larger than it, then save it:
if(now*exchange[j]>now[j])
{
if(j==0)
flag1=1;

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
read the question, "For each table in the input file you must determine whether a sequence of exchanges exists that results in a profit of more than 1 percent (0.01)".

ie. even the input is

2
1.005
1

this one should be considered no solution. i think it's not what your code meant, right?

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
oh,thanks.i misunderstood you,sorry.
i'll fix it tomorrow

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
i fixed that problem and still got WA...

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
so how is your code like now? just in case, can i contact you by email?

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
Who can send the source of this problem(104) to me?
Thanks!!
my-email: hankii@ms10.url.com.tw

Thanks!!!

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Hey, for some code to this, go to http://www.pi.informatik.tu-darmstadt.d ... eme/1/104/ It's not in English but there's like three DIFFERENT solutions there, in C code!!!

LawrenceT
New poster
Posts: 14
Joined: Sun Feb 24, 2002 2:00 am
Location: Singapore
Contact:
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 e-mail 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
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;
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 t-1 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[i-1] then begin
for j:=i to t do sol[j-1]:=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 2002-03-17 17:20 ]</font>

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:
I guess, I didnt understand the problem properly. What about the profit sequences that are of the same length, which should be displayed.

For example in the second sample test case. Why "1 2 4 1" should be displayed among "1 2 3 1" , "1 2 4 1", "2 4 3 2".

Any help is appreciated.

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
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

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:
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 2002-03-24 01:04 ]</font>

ntrhieu
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am

### 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.
Hieu Nguyen

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am