Page 1 of 15
Posted: Tue Dec 04, 2001 11:27 am
dynamic programming? how?

Posted: Wed Dec 05, 2001 4:23 pm
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

Posted: Tue Dec 25, 2001 7:56 pm
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

Posted: Wed Dec 26, 2001 1:15 am
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...

Posted: Sat Dec 29, 2001 7:47 pm
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;
}
}
}

Posted: Sat Dec 29, 2001 7:56 pm
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;
}
}
}

Posted: Sun Dec 30, 2001 8:16 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.

Posted: Sun Dec 30, 2001 9:22 am
I change my program to use * directly instead of +log , but still WA

Posted: Mon Dec 31, 2001 3:45 pm
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.

Posted: Mon Dec 31, 2001 10:15 pm
It still WA when I use my Yahoo account to submit but when I switch to Hotmail, it's accepted, Thank u so much

Posted: Tue Jan 01, 2002 3:53 pm
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.

Posted: Sun Jan 20, 2002 5:42 am
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");
}
}
}

Posted: Sun Jan 20, 2002 7:01 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.

Posted: Sun Jan 20, 2002 8:28 am
really??I thought it must start from 1.
I'll try that,thanks.

Posted: Sun Jan 20, 2002 9:06 am
I fixed it and still get WA...Dont know why