Page 1 of 2

### 436: Arbitrage

Posted: Fri Jun 21, 2002 9:42 am
Did anyone try to solve this using a numerical eigenvalue method? I think
I'll try it, just for fun. Arbitrage is possible iff the largest eigenvalue is
greater than 1, and is equal to limit of the best arbitrage sequence of
length n, raised the the 1/n power, limit as n -> infinity. This will give me
an excuse to learn some things.

For a free book on numerical eigenvalue/eigenvector computation

Posted: Sun Sep 15, 2002 8:42 am
Hi,
Can you please give me some hint behind that how will this work?? I have knowledge of matrix algebra but just unable to see the reason behind.

thanx

### 436-arbitrage-runtime error plz help.

Posted: Sun Apr 24, 2005 7:45 am
My C code is getting runtime error. please some give a hint.

Code: Select all

``````
#include<stdio.h>
#include<string.h>
main()
{
int d=0,found,m,i,j,k,n,in1,in2;
char name[31][500],x[500],y[500];
float c,g[31][31],max;

while(1)
{
scanf("%d",&n);
if(n==0) break;
for(i=1;i<=n;i++)
{
if(i==j) g[i][j]=1;
else 	g[i][j]= 0;
}
for(i=1;i<=n;i++)
scanf("%s",name[i]);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%s%f%s",x,&c,y);  in1=in2=0;
for(j=1;j<=n;j++)
{
if(!strcmp(x,name[j]))
in1=j;
if(!strcmp(y,name[j])) in2=j;
if(in1&&in2) break;
}
g[in1][in2]=c;
}   found=0;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{

if(g[i][k]*g[k][j]>g[i][j]) g[i][j]=g[i][k]*g[k][j];
if(g[i][j]*g[j][i]>1.00001) {found=1;break;}
} if(found) break;
} if(found) break;}

if(found) printf("Case %d: Yes\n",++d);
else printf("Case %d: No\n",++d);
}

}``````

Posted: Fri Apr 29, 2005 10:26 pm
Hello.
I don't know how this code haven't got memory error in your computer.
You just forget this

Code: Select all

``````for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)   // <-------this line
if(i==j) g[i][j]=1;
else    g[i][j]= 0;
}
``````

Posted: Sun May 01, 2005 11:15 am
thanks eduard. you have found the error. i fixed it and got accepted,before. The turbo c++ didn't show any compiletime error! but visual c++ showed.
In hurry i forgot to type the j loop.

### 436 - Arbitrage (II)

Posted: Thu Dec 15, 2005 9:21 pm
Do I understand the thing correctly? Arbitrage, I think, is the condtion when it is possible to make profit by at least one currency using all or less of the given currencies. Isn't it?
I use floyd warshall and then check if for any i,j if dist[j]*dist[j]>1 then it's arbitrage, otherwise not. Ain't I correct?

Posted: Fri Dec 16, 2005 12:36 am
I think your process is right. But are you sure that you are handling presions correctly? Try using dist[j]*dist[j]>1.0001. If you still get WA, you can post your code.

Best of luck.

Posted: Fri Dec 16, 2005 8:28 am
Thanks for your reply. Changing 1.0 to 1.0001 doesn't seem to be enough. Here is my code.

Code: Select all

``DELETED``

Posted: Sat Dec 17, 2005 12:54 am
I think your code is almost ok. I have changed some places and got Accepted.

The places are...

Code: Select all

``````void floyd_warshall(int n){
int i,j,k;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
dist[i][j] = max(dist[i][j], dist[i][k] * dist[k][j]);
}

bool arbitrage(int n){
int i,j;
for(i=0;i<n;i++)
if( dist[i][i]>1.0001)
return true;
return false;
} ``````
Best of Luck.

Posted: Sat Dec 17, 2005 10:44 am
Thanks a lot!

### 436,wa ples help

Posted: Mon Feb 18, 2008 7:41 pm
here is my code:
i don't know whats the problem. someone ples help!!!!!!!!!!!!!

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char str[32][20],str1[20],str2[20];
double str0[32][32];
char str4[20],str3[50],str6[20],str5[20];
main()
{
int n,m,p,q,b,c,i,j,k,flag;
double a,f;
//freopen("436.in","rt",stdin);
p=1;
while(scanf("%d\n",&n)==1)
{
if(n==0)
break;
for(i=0;i<32;i++)
for(j=0;j<32;j++)
str0[i][j]=0.0;

q=0;
while(gets(str[q]))
{
if(q==n-1)
break;
q++;
}
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%s %lf %s",str1,&a,str2);
for(j=0;j<n;j++)
{
if(strcmp(str1,str[j])==0)
b=j;
else if(strcmp(str2,str[j])==0)
c=j;
else
continue;
}
str0[b][c]=a;
}

//scanf("\n");
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{

f=str0[i][k]*str0[k][j];
if(str0[i][j]<f)
str0[i][j]=f;
}
flag=1;
for(i=0;i<n;i++)
{
if(str0[i][i]>1.0001)
{
flag=0;
break;
}
}
if(flag==0)
printf("Case %d: Yes\n",p);
else
printf("Case %d: No\n",p);
p++;
}
}
``````

Posted: Wed Feb 27, 2008 4:14 pm
her just one special things that one should take
input correctly then place the
value to the particular node.

then apply warshel

### Re: 436 - Arbitrage - Clarify please

Posted: Sat Jan 10, 2009 5:44 pm
Hi all.

I'm trying to solve this problem using Floyd Warshall... but I'm getting lots of wrong answers...

I think the problem isn't with the floyd... but perhaps with the input....

I would apreciate if someone could give me some hint or input case that my program fails...

below is my code.

Code: Select all

``````#include <iostream>
#include <map>
#include <stdio.h>
#include <stdlib.h>

#define MAX_V      35
#define inf        0x3f3f3f3f

using namespace std;

double d[MAX_V][MAX_V];

void floyd_warshall(int N);

int main(void) {

int caso=1, npaises;
char msg[2][5];

strcpy(msg[0], "No");
strcpy(msg[1], "Yes");

while (scanf("%d\n", &npaises) && npaises != 0) {
int i, j, dest, qtd, nq, u, v;
double g[MAX_V][MAX_V];
double w;
bool res = 0;
char pais[100], pais1[100], pais2[100];
map<string, int> paises;

for (i=1; i<=MAX_V; i++)
for (j=1; j<=MAX_V; j++)
d[i][j] = 0;

for (i=1; i<=npaises; i++) {
scanf("%s", pais);
paises[string(pais)] = i;
}

scanf("%d\n", &nq);
for (i=1; i<=nq; i++) {
scanf("%s %lf %s\n", pais1, &w, pais2);
d[paises[string(pais1)]][paises[string(pais2)]] = w;
}

floyd_warshall(npaises);

for (i=1; i<=npaises; i++) {
if (d[i][i] > 1.00001) {
res = 1;
break;
}
}

printf("Case %d: %s\n", caso++, msg[res]);
}

return 0;
}

void floyd_warshall(int N) {
int i, j, k;

for (i=1; i<=N; i++) d[i][i] = 1.0;

for (k=1; k<=N; k++)
for (i=1; i<=N; i++)
for (j=1; j<=N; j++) {
d[i][j] = max(d[i][j], d[i][k] * d[k][j]);
}
}
``````

### Re: 436 - Arbitrage - Clarify please

Posted: Fri Apr 17, 2009 1:33 pm
why we should check all dist ?
i checked just dist[n][n] > 1 + eps and i got Acc , is it wrong ?

### Re: 436 - Arbitrage - Clarify please

Posted: Fri Apr 17, 2009 1:53 pm
i think the inputs aren`t tricky enough