104 - Arbitrage

[Alanzo]

dynamic programming? how?

[arnsfelt]

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]

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]

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]

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]

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]

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]

I change my program to use * directly instead of +log , but still WA

[wyvmak]

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]

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]

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]

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]

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]

really??I thought it must start from 1.
I'll try that,thanks.

[FlyDeath]

I fixed it and still get WA...Dont know why