104 - Arbitrage

Moderator: Board moderators

Alanzo
New poster
Posts: 1
Joined: Tue Dec 04, 2001 2:00 am
dynamic programming? how?
arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:
There is a standard graph algorithm that is easily transformed to solve the problem.

To see which and how, transform the conversion rates by the function : x -> -log(x) and reformulate the problem in graph terms.

Kristoffer Hansen
bigredteam2000
New poster
Posts: 11
Joined: Sat Nov 17, 2001 2:00 am
Agian, works with the sample input but when we send it the reply is a wron answer. We use a backtracking algorithm to check all the possible outcomes. First we check if there is a profit in two steps. If there is we find the max profit in two steps and output it. If there is not then we check if there si profit in 3 steps and so on.

//@begin_of_source_code
/*@JUDGE_ID: 15975FF 104 C++*/

#include<iostream.h>

double C[22][22];
int n;
int Steps[22];
int length;
double rate;
double profit;
int Temp[22];
bool flag;

bool CheckTemp(int i, int k)
{
int j;

for( j = 1; j<k; j++)
{
if( Temp[j] ==i)
return false;
}
return true;
}

bool Convert(int k, int j)
{
int i;

rate = 1;
for(i = 2; i <k; i++)
{
rate = rate*C[Temp[i-1]][Temp];
}
rate = rate * C[Temp[k-1]][j];
rate = rate * C[j][1];
if(rate > 1.01)
return true;
return false;
}

void Solve(int k)
{
int i,j;

for(i = 2; i <=n; i++)
{
if(CheckTemp(i,k) && Convert(k,i))
{
if( !flag)
{
Temp[k] = i;
flag = true;
length = k;
profit = rate;
for( j = 1; j <= k; j++)
{
Steps[j] = Temp[j];
}
}
else if(k == length && rate > profit)
{
Temp[k] = i;
profit = rate;
for( j = 1; j <= k; j++)
{
Steps[j] = Temp[j];
}
}
//else if(k < length)
//{
// Temp[k] = i;
// Solve(k+1);
//}
}
}
if(!flag && k < n)
{
for(i = 2; i <=n; i++)
{
if( CheckTemp(i,k))
{
Temp[k] = i;
Solve(k+1);
}
}
}
}

int main()
{
int i,j;

while(cin>>n)
{
for( i = 1; i <=n; i++)
{
for(j = 1; j <=n; j++)
{
if(i == j)
C[j] = 1.0;
else
cin>>C[j];
}
}
flag =false;
profit = 0;
Temp[1] = 1;
Solve(2);
if(flag)
{
for( i = 1; i <=length; i++)
cout<<Steps<< ' ';
cout << 1 <<endl;
}
else
cout<<"no arbitrage sequence exists" << endl;
}

return 0;
}
//@end_of_source_code
Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Try this test:

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

The (one of) correct output is:
5 6 5
10 16 10 16 10

You need to change your algorithm anyway -- your code hangs at second test case...
Cloud
New poster
Posts: 10
Joined: Sat Dec 29, 2001 2:00 am
Contact:
Why WA ?

/* @JUDGE_ID: xxxxx 104 C++ DP */
#include <iostream.h>
#include <math.h>

double a[20][20],d[20][20],tmp,val = log(1.01);
int n,i,j,k,l,tr[20][20],min,path[20];

void main()
{
while (cin >> n)
{
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i == j) a = 0.0;
else
{
cin >> tmp;
if (tmp == 0.0) a[j] = -1e20;
else a[j] = log(tmp);
}
min = n;
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
d[0] = a[k];
tr[0] = k;
}
for (i = 1; i < n; i++)
{
if (i >= min) break;
for (j = 0; j < n; j++) d[j] = -1e20;
for (j = 0; j < n; j++)
for (l = 0; l < n; l++)
if (d[j] < d[i-1][l] + a[l][j])
{
d[j] = d[i-1][l] + a[l][j];
tr[i][j] = l;
}
if (d[i][k] >= val)
{
min = i; j = k; l = i;
while (l >= 0)
{
path[l + 1] = j;
j = tr[l][j];
l--;
}
path[0] = k;
break;
}
}
}
if (min == n + 1) cout << "no arbitrage sequence exists" << endl;
else
{
for (i = 0; i <= min; i++) cout << path[i] + 1 << ' ';
cout << path[min + 1] + 1 << endl;
}
}
}
Cloud
New poster
Posts: 10
Joined: Sat Dec 29, 2001 2:00 am
Contact:
Sorry, I posted a wrong source code in previous message. Here's my WA program :
/* @JUDGE_ID: xxxxx 104 C++ DP */
#include <iostream.h>
#include <math.h>

double a[20][20],d[20][20],tmp,val = log(1.01);
int n,i,j,k,l,tr[20][20],min,path[20];

void main()
{
while (cin >> n)
{
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i == j) a = 0.0;
else
{
cin >> tmp;
if (tmp == 0.0) a[j] = -1e20;
else a[j] = log(tmp);
}
min = n + 1;
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
d[0] = a[k];
tr[0] = k;
}
for (i = 1; i < n; i++)
{
if (i >= min) break;
for (j = 0; j < n; j++) d[j] = -1e20;
for (j = 0; j < n; j++)
for (l = 0; l < n; l++)
if (d[j] < d[i-1][l] + a[l][j])
{
d[j] = d[i-1][l] + a[l][j];
tr[i][j] = l;
}
if (d[i][k] > val)
{
min = i; j = k; l = i;
while (l >= 0)
{
path[l + 1] = j;
j = tr[l][j];
l--;
}
path[0] = k;
break;
}
}
}
if (min == n + 1) cout << "no arbitrage sequence exists" << endl;
else
{
for (i = 0; i <= min; i++) cout << path[i] + 1 << ' ';
cout << path[min + 1] + 1 << endl;
}
}
}
wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
on the first glance, it looks that your program is ok, so the first guess is using log() will cause error in decimal points.
Cloud
New poster
Posts: 10
Joined: Sat Dec 29, 2001 2:00 am
Contact:
I change my program to use * directly instead of +log , but still WA
wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
weird! i cut and paste your 2nd post of code and submit it, it is accepted! and your program performs better than mine too. are you sure you get WA? pls submit again.
Cloud
New poster
Posts: 10
Joined: Sat Dec 29, 2001 2:00 am
Contact:
It still WA when I use my Yahoo account to submit but when I switch to Hotmail, it's accepted, Thank u so much
Orgi
New poster
Posts: 11
Joined: Mon Oct 29, 2001 2:00 am
Location: Bulgaria
You got wrong answer, because the line that contains the message 'no arbitrage sequence exists' is split in two (somewhere at its middle) when you paste it in the yahoo. To avoid this - split the lines which contain long string constants in two shorter lines.

Good luck.
FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
I get right with the test data,but i still get WA

here is my code:

#include <stdio.h>

void main()
{
double now[20];
double next[20];
double exchange[20][20];
int len[20][100];
int i,j,k;
int dim;
int flag=0;
int times=0;
int flag1=0;
while(scanf("%d",&dim)!=EOF)
{
for(i=0;i<20;i++)
{
now=0;
next=0;
for(j=0;j<20;j++)
exchange[j]=0;
for(j=0;j<100;j++)
len[j]=0;
}
for(i=0;i<dim;i++)
{
for(j=0;j<dim;j++)
{
if(i==j)
continue;
scanf("%lf",&exchange[j]);
}
}
now[0]=1;
next[0]=1;
for(i=1;i<dim;i++)
{
now=exchange[0];
next=exchange[0];
}
for(i=0;i<dim;i++)
len[0]=i+1;
times=0;
flag1=0;
while(1)
{
times++;
flag=0;
for(i=0;i<dim;i++)
{
for(j=0;j<dim;j++)
{
if(now[i]*exchange[i][j]>now[j])
{
if(j==0)
flag1=1;
next[j]=now[i]*exchange[i][j];
for(k=0;k<times;k++)
len[j][k]=len[i][k];
len[j][times]=j+1;
flag=1;
}
}
}
for(j=0;j<dim;j++)
now[j]=next[j];
if(flag1==1)
break;
if(flag==0)
break;
}
if(flag==0)
printf("no arbitrage sequence existsn");
else if(flag1==1)
{
printf("1");
for(i=0;i<=times;i++)
printf(" %d",len[0][i]);
printf("n");
}
}
}
wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
on the first glance, if not overlooked, your printf("1"); gives me a feeling that your sequence must be started (and ended) with 1, but seems that you can start with any other, 2, 3... etc.
FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
really??I thought it must start from 1.
I'll try that,thanks.
FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
I fixed it and still get WA...Dont know why