104 - Arbitrage

[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]

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]

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]

oh,thanks.i misunderstood you,sorry.
i'll fix it tomorrow

[FlyDeath]

i fixed that problem and still got WA...

[wyvmak]

so how is your code like now? just in case, can i contact you by email?

[hank]

Who can send the source of this problem(104) to me?
Thanks!!
my-email: hankii@ms10.url.com.tw

Thanks!!!

[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]

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]

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]

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]

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]

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]

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.

[C8H10N4O2]

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