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

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

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

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

New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Contact:

436-arbitrage-runtime error plz help.

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,x,y;
float c,g,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
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

New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Contact:
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
Contact:

436 - Arbitrage (II)

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
Contact:
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
Contact:
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
Contact:
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
Contact:
Thanks a lot! turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm

436,wa ples help

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,str1,str2;
double str0;
char str4,str3,str6,str5;
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
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

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;

strcpy(msg, "No");
strcpy(msg, "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, pais1, pais2;
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
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 436 - Arbitrage - Clarify please

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

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

Re: 436 - Arbitrage - Clarify please

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