104 - Arbitrage

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Alanzo
New poster
Posts: 1
Joined: Tue Dec 04, 2001 2:00 am

Post by Alanzo » Tue Dec 04, 2001 11:27 am

dynamic programming? how?

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » 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

bigredteam2000
New poster
Posts: 11
Joined: Sat Nov 17, 2001 2:00 am

Post by bigredteam2000 » 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

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » 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...

Cloud
New poster
Posts: 10
Joined: Sat Dec 29, 2001 2:00 am
Contact:

Post by Cloud » Sat Dec 29, 2001 7:47 pm

Why WA ? :sad:

/* @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:

Post by Cloud » 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;
}
}
}

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » 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.

Cloud
New poster
Posts: 10
Joined: Sat Dec 29, 2001 2:00 am
Contact:

Post by Cloud » Sun Dec 30, 2001 9:22 am

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

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » 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.

Cloud
New poster
Posts: 10
Joined: Sat Dec 29, 2001 2:00 am
Contact:

Post by Cloud » 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 :smile:

Orgi
New poster
Posts: 11
Joined: Mon Oct 29, 2001 2:00 am
Location: Bulgaria

Post by Orgi » 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.

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » 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");
}
}
}

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » 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.

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Sun Jan 20, 2002 8:28 am

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

Post by FlyDeath » Sun Jan 20, 2002 9:06 am

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

Post Reply

Return to “Volume 1 (100-199)”