436 - Arbitrage (II)

[Cubist]

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
grab Saad's book:

http://www-users.cs.umn.edu/~saad/books.html

[17933PN]

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

[adnan2nd]

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);
 }

}

[Eduard]

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; 
  }   

[adnan2nd]

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.

[mamun]

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?

[Jan]

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.

[mamun]

Thanks for your reply. Changing 1.0 to 1.0001 doesn't seem to be enough. Here is my code.

Code: Select all

DELETED

[Jan]

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.

[mamun]

Thanks a lot!

[turcse143]

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++;
	}
}

[turcse143]

i already got AC.
her just one special things that one should take
input correctly then place the
value to the particular node.

then apply warshel

[JohnTortugo]

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]);
              }
}

[vahid sanei]

why we should check all dist ?
i checked just dist[n][n] > 1 + eps and i got Acc , is it wrong ?

[vahid sanei]

i think the inputs aren`t tricky enough