## 104 - Arbitrage

Moderator: Board moderators

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
for output we just print a sequence with profit more than 1 percent with minimal sequence, not the best profit only. So there are many correct answer for the third input : 1 2 4 1, 1 2 3 1, 2 4 3 2.

GOOD LUCK.

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

### 104 TLE

i'm trying to solve this problem using the Floyd-Warshall algorithm, but jufge replies me TLE anyway, can anybody helpp me plz? thx a lot
this is my code:
[cpp]

/* @JUDGE_ID: xxxxxxx 104 C++ */
/* @BEGIN_OF_SOURCE_CODE */

//#import <iostream>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

typedef pair<double, vector<int> > P;
typedef vector<P> V;
typedef vector<V> V2;

void printar(vector<int> v)
{
for(int i = 0; i< v.size(); i++)
cout << v+1 << " ";
cout << endl;
}

vector<int> concat(vector<int> v, vector<int> w)
{
for(int i = 1; i< w.size(); i++)
v.push_back(w);
return v;
}

P func_aux(P p)
{
vector<int> v = p.second;
double d = p.first;
int count = 0;
while(d < 1.01 && v.size() < 20)
{
d = d*p.first;
v = concat(v,p.second);
}
p = make_pair(d,v);
return p;
}

P optim(P p1, P p2, P p3)
{
vector<int> aux;
double a = p1.first, b = p2.first*p3.first;
P sor = make_pair(b,concat(p2.second,p3.second));
if(b > 1 && b < 1.01)
sor = func_aux(sor);
if(a >= 1.01 && b < 1.01)
return p1;
else if(a < 1.01 && b >= 1.01)
return sor;
else if(a >= 1.01 && b >= 1.01 && p1.second.size() < sor.second.size())
return p1;
else if(a >= 1.01 && b >= 1.01 && p1.second.size() > sor.second.size())
return sor;
else if(a >= 1.01 && b >= 1.01 && p1.second.size() == sor.second.size() && a > b)
return p1;
else if(a >= 1.01 && b >= 1.01 && p1.second.size() == sor.second.size() && a < b)
return sor;
else if(a >= 1.01 && b >= 1.01 && p1.second.size() == sor.second.size() && a == b)
return sor;
else if(a < 1.01 && b < 1.01 && a > b)
return p1;
else if(a < 1.01 && b < 1.01 && a < b)
return sor;
else
return p1;
}

vector<int> proces(int tam)
{
V2 str(tam, V(tam));
vector<int> aux(2);
double temp;
int origen, desti;
for(origen = 0; origen < tam; origen++)
{
for(desti = 0; desti < tam; desti++)
{
aux =origen;
aux = desti;
if(origen == desti)
temp = 1;
else
cin >> temp;
str[origen][desti] = make_pair(temp, aux);
}
}
for(int auxiliar = 0; auxiliar < tam; auxiliar++)
{
for(origen = 0; origen < tam; origen++)
{
for(desti = 0; desti < tam; desti++)
{
if(auxiliar != origen && auxiliar != desti)
str[origen][desti] = optim(str[origen][desti], str[origen][auxiliar], str[auxiliar][desti]);
}
}
}
aux.clear();
for(int i = 1; i< tam; i++)
{
if(str.first >= 1.01)
{
if(aux.size() == 0)
aux = str.second;
else if(aux.size() > str.second.size())
aux = str.second;
}

}
return aux;
}

main()
{
int tam;
vector<int> sor;
while(cin >> tam)
{
sor = proces(tam);
if(sor.size() == 0 )
cout << "no arbitrage sequence exists" << endl;
else
printar(sor);
}
return 0;
}
/*@END_OF_SOURCE_CODE*/

[/cpp]

KURAPICA
New poster
Posts: 3
Joined: Wed Jul 30, 2003 4:23 am

### can somebody help me?Prob.104

here is my code
[c]int Path;
printpath(int i,int j)
{
if(i!=j) printpath(i,Path[j]);
printf("%d ",j+1);
}
main()
{
double conv;
int n,i,j,k,arbitrage;
while(scanf("%d",&n)==1){
arbitrage=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++){
if(i==j) conv[j]=1;
else scanf("%lf",&conv[j]);
Path[j]=i;
}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(conv[k]*conv[k][j]>conv[j]){
conv[j]=conv[k]*conv[k][j];
Path[j]=Path[k][j];
}
for(i=0;i<n;i++){
if(conv[i]>1.01){
printpath(i,Path[i][i]);/*printf_path(i,i) will have space*/
printf("%d\n",i+1);
arbitrage=1;break;
}
}
if(!arbitrage) printf("no arbitage sequence exists\n");
}
}
[/c]
but i got:Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.057 seconds. epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
this problem seems interesting, i will try to solve it.

i have 2 things to tell you:

1) the error you get means your program is incorrect, which has nothing to do with what the program actually does, but how it is written.

2) your algorithm seems incorrect too. let me explain:

imagine there are 20 currencies, and you notice the loop 121 gives you a 0.1% profit. it's not a big enough profit, but you could loop several times since you are allowed 20 trades:
1 2 1 2 1 2 1 2 1 ... 2 1 would eventually give you a profit greater than 1%. it seems your program wouldn't detect it though. hope that helps

good luck, keep trying!
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

wonderboy
New poster
Posts: 4
Joined: Thu Oct 17, 2002 10:21 pm
Location: India
Contact:

Hello everyone,
I am fed up of getting Runtime Error (SIGSEGV; invalid memory reference) for this problem. I have used the Floyd-Warshall algo. I checked with the other posts related to this prob and have tested my program thouroughly and it runs fine in my system. But for some reason OJ says a Runtime Error. Infact i have increased my array sizes to ensure no invalid memory reference occurs. But still i get the same result. Maye i m missing something trivial. PLEASE help me in finding it. Thank you for ur help.

Code: Select all

``````[cpp]

#include <iostream>
#include <cstdlib>

using namespace std;

void printpath(int i,int j,long double prod);

long double exchange;
int p;
long double c;

int main()
{
int i,j,k;
int n;
bool found;
long double prod=1;

while(cin>>n)
{

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)
{
c[i][j]=exchange[i][j]=1;
p[i][j]=i;
}
else
{
p[i][j]=i;
cin>>c[i][j];
exchange[i][j]=c[i][j];
}
}
}

found=false;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(c[i][j]>=(c[i][k]*c[k][j]))
{
c[i][j]=c[i][j];
p[i][j]=p[i][j];
}
else
{
c[i][j]=c[i][k]*c[k][j];
p[i][j]=p[k][j];
}

if(i==j && c[i][j]>1.01)
{
found=true;
printpath(i,j,prod);
cout<<"\n";
break;
}

}
if(found)
break;
}
if(found)
break;
}

if(!found)
cout<<"no arbitrage sequence exists\n";

}

return 0;
}

void printpath(int i,int j,long double prod)
{
if(i>120 || j>120)
return;
if(i==j && prod>1.01)
cout<<i;
else
{
prod*=exchange[p[i][j]][j];
printpath(i,p[i][j],prod);
cout<<" "<<j;
}
}
[/cpp]``````

secret-mission
New poster
Posts: 4
Joined: Tue Jul 29, 2003 10:56 am

### p104 (Arbitrage) - Pascal - TLE - Tested [Unsolved]

I have read all of the topic which is posted before. And i still get TLE. I use BFS to solve this problem. Any idea?

[pascal]
(* @begin_of_source_code *)
program p104(input,output);
{\$IFDEF ONLINE_JUDGE}
type tint = integer;
{\$ELSE}
type tint = longint;
var input : text;
{\$IFDEF FILE}
var output : text;
{\$ENDIF}
{\$ENDIF}
type
tdata = array[1..20,1..20] of real;
tdata2 = array[1..20,1..2] of tint;
tstep = array[1..20] of tint;
tlog = array[1..20] of boolean;
var
data : tdata;
data2 : tdata2;
hasil,step : tstep;
log : tlog;
i,j,total,lhasil,maxb,max2b : tint;
max,max2 : real;
suc : boolean;
s : boolean;
procedure init(i:tint;step:tstep;curstep:tint;log:tlog;sum:real);
var
step2 : tstep;
j,n : tint;
begin
if (curstep > 1) and (sum*data[step[curstep],step] > 1) then
begin
if (sum*data[step[curstep],step]-1)*100 < 1 then
begin
sum := sum*data[step[curstep],step];
inc(curstep);
step[curstep] := step;
n := curstep;
step2 := step;
while (sum-1)*100 < 1 do
begin
for j := 2 to curstep do
begin
inc(n);
step2[n] := step[j];
sum := sum*data[step[j-1],step[j]];
end;
end;
step := step2;
curstep := n;
end
else
begin
inc(curstep);
step[curstep] := step;
end;
hasil := step;
lhasil := curstep;
s := true;
end
else if not s then
begin
if (i <> data2[i,1]) and (not log[data2[i,1]]) then
begin
step[curstep+1] := data2[i,1];
log := true;
init(data2[i,1],step,curstep+1,log,sum*data[i,data2[i,1]]);
log := false;
end
else if (not log[data2[i,2]]) then
begin
step[curstep+1] := data2[i,2];
log := true;
init(data2[i,2],step,curstep+1,log,sum*data[i,data2[i,2]]);
log := false;
end;
end;
end;
begin
{\$IFNDEF ONLINE_JUDGE}
assign(input,'p104.in');
reset(input);
{\$IFDEF FILE}
assign(output,'p104.out');
rewrite(output);
{\$ENDIF}
{\$ENDIF}
while not eof(input) do
begin
suc := true;
if (total > 20) or (total < 2) then suc := false;
if suc then
begin
for i := 1 to total do
begin
max := 0;
max2 := 0;
for j := 1 to total do
begin
if i = j then data[i,j] := 1
else
begin
if i <> total then
begin
if i <> total then read(input,data[i,j])
end
else
begin
if i <> total-1 then read(input,data[i,j])
end;
end;
if max = 0 then
begin
max := data[i,j];
maxb := j;
end
else
begin
if data[i,j] > max then
begin
max2 := max;
max2b := maxb;
max := data[i,j];
maxb := j;
end;
end;
end;
if max <> 0 then data2[i,1] := maxb;
if max2 <> 0 then data2[i,2] := max2b;
end;
s := false;
lhasil := 0;
for i := 1 to total do log := false;
for i := 1 to total do
begin
if s then break;
step := i;
init(i,step,1,log,1);
end;
if lhasil <> 0 then
begin
for i := 1 to lhasil do
begin
if i <> lhasil then write(output,hasil:1,' ')
else writeln(output,hasil:1);
end;
end
else writeln(output,'no arbitrage sequence exists':1);
end;
end;
{\$IFNDEF ONLINE_JUDGE}
{\$IFDEF FILE}
close(output);
{\$ENDIF}
close(input);
{\$ENDIF}
end.
(* @end_of_source_code *)
[/pascal]

input

2
2.0
0.45
2
1.005
1
2
1.1
0.915
3
1.2 .89
.88 5.1
1.1 0.15
4
1.0 1.0 1.0
1.007 1.0 1.0
1.0 1.0 1.0
1.0 1.0 1.0
4
3.1 0.0023 0.35
0.21 0.00353 8.13
200 180.559 10.339
2.11 0.089 0.06111
6
0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.1 0.0 0.0
0.0 0.0 1.0 0.0 0.0
0.0 5.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 9.0
0.0 0.0 0.0 0.0 1.0
20
0.38 0.88 0.33 0.85 0.76 0.62 0.15 0.69 0.42 0.96 0.19 0.62 0.54 0.90 0.95 0.08 0.99 0.78 0.42
0.51 0.86 0.43 0.20 0.21 0.27 0.24 0.21 0.20 0.37 0.11 0.74 0.50 0.44 0.52 0.71 0.62 0.49 1.03
0.51 0.06 0.83 0.68 0.60 0.48 0.37 0.11 0.15 0.68 0.47 0.54 0.63 0.80 0.49 0.23 0.87 1.03 0.57
0.37 0.62 0.55 0.94 0.58 0.61 0.09 0.85 0.69 0.78 0.92 0.89 0.76 0.46 0.25 0.83 0.21 0.49 0.12
0.01 0.40 0.31 0.09 0.38 0.42 1.03 0.81 1.00 0.04 0.91 0.46 0.21 0.41 0.05 0.65 0.69 0.84 0.70
0.88 1.04 0.69 0.38 0.61 0.57 0.36 0.24 0.72 0.12 0.95 0.71 0.98 0.56 0.34 0.76 0.33 0.68 0.94
0.03 0.40 0.73 0.70 0.25 0.24 0.41 0.92 0.71 0.87 0.23 0.75 0.76 0.59 0.51 1.00 0.55 0.62 0.70
0.65 0.72 0.95 0.65 0.40 0.99 0.59 0.25 0.85 0.80 0.45 0.64 0.46 0.36 0.77 0.28 0.92 0.24 0.92
0.78 0.49 0.05 0.01 0.73 0.06 0.98 0.67 0.29 0.27 0.48 0.43 0.46 0.61 0.71 0.76 0.56 0.28 0.33
0.81 0.73 0.92 0.16 0.97 0.77 1.03 0.86 0.38 0.62 0.89 0.48 0.45 0.08 1.04 0.76 0.11 0.20 0.18
0.63 0.70 0.49 0.64 0.73 0.51 0.41 0.51 0.35 0.31 0.33 0.75 0.10 0.84 0.94 0.90 1.02 0.33 0.80
0.67 0.57 0.94 0.86 0.02 0.67 0.14 0.49 0.75 0.82 0.41 0.28 0.45 0.31 0.31 0.32 0.21 0.03 0.78
0.26 0.88 0.17 0.01 0.56 0.04 0.93 1.04 0.79 0.39 0.36 0.69 0.65 0.80 0.99 0.30 0.42 1.00 0.99
0.42 0.10 0.00 0.35 0.38 0.56 0.64 1.01 0.67 0.55 0.56 0.41 0.05 0.16 0.42 0.74 0.40 0.26 0.83
0.58 1.03 0.66 0.16 0.84 0.06 0.69 1.04 0.62 0.77 0.98 0.67 0.50 0.05 0.74 0.60 0.89 0.91 1.03
0.57 0.68 0.95 0.99 0.27 0.14 1.02 0.34 0.23 0.97 0.22 0.66 0.70 0.09 0.64 0.20 0.39 0.14 1.04
0.37 0.14 0.50 0.64 0.30 0.17 1.00 1.01 0.98 0.34 1.03 0.72 0.94 0.67 0.74 0.82 0.75 0.57 0.69
0.84 0.29 0.53 0.01 0.77 0.09 0.93 0.94 0.11 0.32 0.36 0.11 1.00 0.38 0.30 0.74 0.80 0.77 0.94
0.04 0.48 0.97 0.54 0.81 0.33 0.67 0.10 0.83 0.94 0.22 0.52 0.90 0.62 0.79 0.90 0.40 0.26 0.23
0.55 0.48 0.75 0.96 0.65 0.21 0.98 0.71 0.91 0.63 0.94 0.62 0.56 0.90 0.89 0.00 0.43 0.43 0.08

output

no arbitrage sequence exists
1 2 1 2 1
1 2 1 2 1
1 2 1
2 1 2 1 2
1 2 4 1
5 6 5
10 16 10 16 10

i hope to hear your idea as soon as possible.

Best Regards.

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

### Problem 104, 120 WA

Problem 104.

shortest path in profit of more than 1%, is right ?

only more than 1%

please, give me the some input and output examples..

Problem 120.

it is necessary to find the optimal solution?

it is only to make sorted stack, is right ?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
About 120 - Stacks of Flapjacks
------------------------------------

Yes, any solution would be acceptable. You do not have to find the optimal one.

When there is a yellow tick, it means it has a correction program associated with it. And thus any solution not exceeding the time limit, or memory limit would be AC.

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

### Thanx

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

### hm. still i get WA ,

I don't know, why this source code is wrong.
Help me, anybody plz.

Code: Select all

``````#include <stdio.h>

int Array={0,};
int N ;

void print()
{
int Loop1;
printf("\n");
for (Loop1=0 ; Loop1<N ; Loop1++)
printf("%d ", Array[Loop1]);
}

void Flip(int pos )
{
int Temp ;
int Loop1;
for (Loop1=0 ; Loop1<(pos+1)/2 ; Loop1++)
{
Temp = Array[Loop1] ;
Array[Loop1] = Array[pos-Loop1] ;
Array[pos-Loop1] = Temp ;
}
printf("%d ", N-pos);
}

int FindMax(int pos )
{
int index = 0 ;
int Loop1;

for (Loop1=1 ; Loop1<=pos ; Loop1++)
if ( Array[index] < Array[Loop1] ) index = Loop1;

return index ;
}

void main()
{
char input={0,};
int Pos=0;
int Loop1;

while ( gets(input) != NULL )
{
printf("%s\n", input);
for (Loop1=0 ; sscanf(input, "%d %[^\0]", &Array[Loop1], input) == 2 ; Loop1++);
N = Loop1+1 ;
Pos = 0 ;

for (Loop1=N-1; Loop1>0 ; Loop1--)
{
Pos = FindMax(Loop1);
if ( Pos == Loop1 ) continue ;
else if ( Pos == 0 ) Flip(Loop1);
else
{
Flip(Pos);
Flip(Loop1);
}
}

printf("0\n");
}
}
``````
[/code]

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am

### Are you getting WA for prob 104?

Hi, I just started trying these programming challenges a few days ago...I find them pretty tough! But that's why I like them!

Anyway, if, like me, you keep getting WA on question 104, here's a test case that may help you...my first program gave the correct answer for all test cases I could find, but still wasn't accepted. I was trying to use the Floyd-Warshall algorithm, but I didn't really understand how it worked...when I rewrote the program from scratch it was accepted! this test case gave different answers on the two versions:

3
0.1 2
2 0.1
2 2

The answer should be 1 3 1 (or 3 1 3)...but your program might give
1 3 2 1. This has a higher profit but is wrong because it involves more transactions.

Hopefully this helps someone!

40366
New poster
Posts: 4
Joined: Wed Jan 07, 2004 9:42 am

### arbitage vol 1

i dont clearly understand the qn
say that a cyle 1 2 1 gives .04% profit
the is cycle 12112121 also valid arbitage seq (the length of cycle is less than the no of countries)
Last edited by 40366 on Thu Jan 08, 2004 5:35 am, edited 2 times in total.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
It is said on the problem that if 2 or more sequences exists that gave profit more than 1%, print the sequence of minimal length.

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). If a sequence exists you must print the sequence of exchanges that results in a profit. If there is more than one sequence that results in a profit of more than 1 percent you must print a sequence of minimal length, i.e., one of the sequences that uses the fewest exchanges of currencies to yield a profit.

hope it helps

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands
Hi Gambit,

I used the following plan for my AC program:

The most profitable way to go from A to Z in n steps which goes through the highest yielding currency H at step n-1 is:
P(A,Z,n) = P(Z,H,n-1) + P(H,Z,1)

So, at every step I take as base the path from A to H and expand the path with the next exchange which yields the most profit.

Continue taking steps as long as P(A,A,n) < 1.01 and n < total currencies.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
You build up your matrix exchange by exchange.

So, after 1 exchange, the maximum profit would be:

1.000 1.200 0.890
0.880 1.000 5.100
1.100 0.150 1.000

And after another exchange:

1.056 1.200 6.120
5.610 1.056 5.100
1.100 1.320 1.000

This says I can get 1.056 from currency 1 to currency 1 in two exchanges (namely, 1->2 and 2->1).

Also, you could interpret it as getting 6.120 of currency 3 from 1.000 of currency 1 through (at most) 2 exchanges, (namely, 1->2->3), which is better than (1->3), so by this way of stepping through each level of exchanges, you eliminate the shorter paths that wouldn't yield the best profits up to that point.[/java][/code]