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

Post by wyvmak »

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

Post by FlyDeath »

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

Post by wyvmak »

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

Post by FlyDeath »

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

Post by FlyDeath »

i fixed that problem and still got WA...

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak »

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.

Post by hank »

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:

Post by paulhryu »

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:

Post by LawrenceT »

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.

vlad ionescu
New poster
Posts: 2
Joined: Sun Mar 17, 2002 2:00 am

Post by vlad ionescu »

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

Post by ram »

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

Post by Ivor »

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:

Post by ram »

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

Post by ntrhieu »

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
Location: Pasadena, CA

Post by C8H10N4O2 »

An 3D implementation of Floyd-Warshall should also work:o)

Post Reply

Return to “Volume 1 (100-199)”