436 - Arbitrage (II)

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

Moderator: Board moderators

Cubist
New poster
Posts: 17
Joined: Sun May 26, 2002 7:56 am
Location: San Diego, CA

436: Arbitrage

Post by Cubist » 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. :D

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

http://www-users.cs.umn.edu/~saad/books.html
Chris Long, San Diego Padres, 100 Park Boulevard, San Diego CA

My captain is Stanley Tweedle. I blow up planets for him.

17933PN
New poster
Posts: 3
Joined: Wed Sep 11, 2002 7:59 pm

please explain

Post by 17933PN » 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

adnan2nd
New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Location: bangladesh,ctg
Contact:

436-arbitrage-runtime error plz help.

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

}
sobhani

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » 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; 
  }   
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

adnan2nd
New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Location: bangladesh,ctg
Contact:

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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

436 - Arbitrage (II)

Post by mamun » 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?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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.
Ami ekhono shopno dekhi...
HomePage

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » 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
Last edited by mamun on Sat Dec 17, 2005 10:43 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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.
Ami ekhono shopno dekhi...
HomePage

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sat Dec 17, 2005 10:44 am

Thanks a lot! :D

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

436,wa ples help

Post by turcse143 » 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++;
	}
}
''I want to be most laziest person in the world''

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Wed Feb 27, 2008 4:14 pm

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
''I want to be most laziest person in the world''

JohnTortugo
New poster
Posts: 18
Joined: Sun Jul 20, 2008 7:05 pm

Re: 436 - Arbitrage - Clarify please

Post by JohnTortugo » 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]);
              }
}

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 436 - Arbitrage - Clarify please

Post by vahid sanei » 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 ?
Impossible says I`m possible

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 436 - Arbitrage - Clarify please

Post by vahid sanei » Fri Apr 17, 2009 1:53 pm

i think the inputs aren`t tricky enough
Impossible says I`m possible

Post Reply

Return to “Volume 4 (400-499)”