Page 1 of 2

436: Arbitrage

Posted: Fri Jun 21, 2002 9:42 am
by 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. :D

For a free book on numerical eigenvalue/eigenvector computation
grab Saad's book:

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

please explain

Posted: Sun Sep 15, 2002 8:42 am
by 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

436-arbitrage-runtime error plz help.

Posted: Sun Apr 24, 2005 7:45 am
by 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);
 }

}

Posted: Fri Apr 29, 2005 10:26 pm
by 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; 
  }   

Posted: Sun May 01, 2005 11:15 am
by 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.

436 - Arbitrage (II)

Posted: Thu Dec 15, 2005 9:21 pm
by 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?

Posted: Fri Dec 16, 2005 12:36 am
by 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.

Posted: Fri Dec 16, 2005 8:28 am
by 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

Posted: Sat Dec 17, 2005 12:54 am
by 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.

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

436,wa ples help

Posted: Mon Feb 18, 2008 7:41 pm
by 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++;
	}
}

Posted: Wed Feb 27, 2008 4:14 pm
by 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

Re: 436 - Arbitrage - Clarify please

Posted: Sat Jan 10, 2009 5:44 pm
by 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]);
              }
}

Re: 436 - Arbitrage - Clarify please

Posted: Fri Apr 17, 2009 1:33 pm
by vahid sanei
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
by vahid sanei
i think the inputs aren`t tricky enough