104 - Arbitrage

[nafi1212]

Many Many thanx to ImLazy and gits. But, ImLazy, U forgot to remove code.
R u really that lazy??

[kbr002]

I do not quite understand this:

Code: Select all

#define T(_I, _J) table[_I+(_J<<5)]
...
double table[32<<5]; 

Could somebody explain it?

[huan086]

Is there something wrong with my method? I try to maximise the conversion from i to j at every step, then check the diagonal values in the table.

my output is this

10 16 10 16 10
1 2 1
1 2 4 1
no arbitrage sequence exists
5 6 5
no arbitrage sequence exists
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1
no arbitrage sequence exists
no arbitrage sequence exists

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	const double EPS = 1e-13;
	int i, j, k, l, expected, index;
	double convTable[21][21];
	double orgConvTable[21][21];
	char route[21][21][21];
	int routeLen[21][21];
	int numOfCountries;
	int found, changed;

	/*freopen("in.txt", "rt", stdin);
	freopen("out.txt", "wt", stdout);*/

	while (scanf(" %d", &numOfCountries) == 1)
	{
		memset(routeLen, 0, sizeof(routeLen));
		found = 0;
		changed = 0;
		for (i = 0; i < numOfCountries; ++i)
		{
			for (j = 0; j < numOfCountries; ++j)
			{
				if (i == j)
					convTable[i][j] = (double)1.0;
				else
				{
					scanf(" %Lf", &convTable[i][j]);
					orgConvTable[i][j] = convTable[i][j];
				}
			}
		}

		for (expected = 0; expected < numOfCountries - 1; ++expected) /* expected route length */
		{
			for (i = 0; i < numOfCountries; ++i) /* maximise conversion from i to j and i to i */
			{
				for (j = 0; j < numOfCountries; ++j)
				{
					double max = convTable[i][j];
					double t;
					int tempk;
					for (k = 0; k < numOfCountries; ++k)
					{
						if (j == k) /* orgConvTable[k][j] is always 1 */
							continue;
						if (routeLen[i][k] == expected)
						{
							t = convTable[i][k] * orgConvTable[k][j];
							if (t > max)
							{
								max = t;
								tempk = k;
								changed = 1; /* this set might have a solution */
							}
						}
					}
					if (convTable[i][j] != max)
					{
						convTable[i][j] = max;
						for (k = 0; k < routeLen[i][tempk]; ++k)
						{
							route[i][j][k] = route[i][tempk][k];
						}
						route[i][j][k] = tempk;
						routeLen[i][j] = expected + 1;
					}
				}
			}

			/* find if 0.01 profit can be made converting i to i */
			for (i = 0; i < numOfCountries; ++i)
			{
				if (convTable[i][i] - (double)1.01 > EPS)
				{
					found = 1;
					index = i;
					break;
				}
			}
			if (!changed)
				break;
			if (found)
				break;
		}
		if (!found)
			printf("no arbitrage sequence exists\n");
		else
		{
			printf("%d", index + 1);
			for (i = 0; i < routeLen[index][index]; ++i)
			{
				printf(" %d", route[index][index][i] + 1);
			}
			printf(" %d\n", index + 1);
		}
	}
	return 0;
}

[huan086]

never mind. found my logic error. I have been overwriting values i still need in the next iteration, which had cause my program to miss out arbitrage sequence like 1 4 3 2 1.

Thanks to all who had tried to debug

[huan086]

1 more test case here in case you made the same logic error as me

Input:

Code: Select all

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455
1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455

Output:

Code: Select all

1 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

[lena]

anybody who tell tell me why?????
my code is below~~

/////////////////////////////////////////

#include<stdio.h>
#include<vector>
using namespace std;

#define M 20

float a[M][M];
int b[M][M];
int c[M][M];
int n;
int res[M];

void solve()
{
int i,j,k;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[j]<a[k]*a[k][j])
{
a[j] = a[k]*a[k][j];
b[j] = b[k][j];
c[j] = c[k]+c[k][j];
}else if(a[j] == a[k]*a[k][j] && c[j]> c[i][k]+c[k][j])
{
b[i][j] = b[k][j];
c[i][j] = c[i][k] + c[k][j];
}
for(i=0;i<n;i++)
if(a[i][i]>1.01)
break;
if(i>=n)
printf("no arbitrage sequence exists\n");
else
{
int s = i;
i ++;
for(;i<n;i++)
{
if(a[i][i]>1.01 && c[i][i]<c[s][s])
s = i;
}
i = s;
vector<int> res;
res.clear();
j = i;
res.push_back(i+1);
while(b[i][j]!=i)
{
res.push_back(b[i][j]+1);
j = b[i][j];
}
printf("%d",i+1);
for(j=0;j<res.size();j++)
printf(" %d",res[res.size()-1-j]);
printf("\n");

}
}
int main()
{
//freopen("104.txt","r+",stdin);
while(scanf("%d",&n)!=-1)
{
int i,j;
for(i = 0;i<n;i++)
for(j=0;j<n;j++)
{
a[i][j] = 0;
b[i][j] = i;
c[i][j] = 1;
}

for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=j)
scanf("%f",&a[i][j]);
solve();
}
//while(true){}
return 0;
}

[shamim]

The problem lies in the function solve().
The res vector grows beyond capacity.

[lena]

oh,you means the default capacity of vector? i will try it.

[shamim]

Actually, I meant it grows without bound. That means, it grows to such an extent that, it occupies more memory than allowed by UVA Judge.

[sandy007smarty]

@gits:
I got AC, but I have this doubt.

tmp = best[k][steps-1] * best[k][j][1]

I feel the above statement should be:-

Code: Select all

best[i][k][steps-m]*best[k][j][m]

and m should vary from 1 to steps-1 (making the solution O(n^5)).

But why is it not required? Why is just calculating for m=1 enough?

[andysoft]

Hello!
I have been hunting this problem for really long, but I get WA every time, and there were a lot of these times.
Can anyone gimme a hint (cause I completly have no idea) where the bug in my prog lies...

Code: Select all

program Project2;

{$APPTYPE CONSOLE}
{$R-}{$S-}{$Q-}
type
  integer = longint;
var
  a: array [1..20,1..20] of extended;
  b: array [1..20,1..20,1..20] of extended;
  p: array [1..20,1..20,1..20] of integer;
  seq: array [1..20] of integer;
  i,j,k,l,m,n: integer;
  col: integer;
  i1: integer;
  fl: boolean;


begin

  while not eof do
  begin
    n := -1;
    readln (n);
    if n<1 then
      break;
    for i := 1 to 20 do
      for j := 1 to 20 do
      begin
        a[i,j] := 1.0;
        b[i][j][1] := 1;
        for l := 2 to n do
          b[i][j][l] := 0
      end;



    for i := 1 to n do
    begin
        j:=0;
        while j<n do
        begin
          j := j + 1;
          if j=i then continue;
          read (a[i,j]);
          b[i][j][1] := a[i][j];
          p[i][j][1] := i;
        end
    end;

    for l := 2 to n do
      for k := 1 to n do
        for i := 1 to n do
          for j := 1 to n do
            if b[i][k][l-1]*b[k][j][1] > b[i][j][l] then
            begin
              b[i][j][l] := b[i][k][l-1]*b[k][j][1];
              p[i][j][l] := k
            end;

    fl := false;
    for l := 2 to n do
    begin
      for i := 1 to n do
        if b[i][i][l]>1.01 then
        begin
          seq[l] := p[i][i][l];
          for m := l-1 downto 1 do
            seq [m] := p[i][seq[m+1]][m];
          for j := 1 to l do
            write (seq[j],' ');
          writeln (i);
          fl := true;
          break;
        end;
        if fl then
          break        
    end;
        
    if not fl then
      writeln ('no arbitrage sequence exists');            
          
  end;




end.

[cpp_stu2]

see this page
http://online-judge.uva.es/board/viewto ... 0923#30923
It may helps

[kwdikosno8]

can someone explain me why ImLazy's code is O(n^3)) ?
can someone explain me step by step how can u find the coplexity?

[shady_mokhtar]

i am solving it brute force using binary numbers by a loop till 1<<n (1^20=1048576) so it doesn't take so much time...here is my code check it please

Code: Select all

#include<iostream.h>

int main()
{
	int flag,s,i,j,t,n,seq[22],finseq[22],maxx,l,f,k;
	double mult,table[21][21];
	while(cin>>n)
	{
		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		if(i==j)
		table[i][j]=1.0;
		else
		cin>>table[i][j];
		
    	finseq[0]=-1;	
		maxx=60;
		for(i=3;i<(1<<n);i++)
		{
			t=i; s=0; mult=1.0; l=-1; f=-1; k=0; flag=0;
			while(t!=0)
			{
				if(t%2==1)
				{
					if(l==-1)
					f=s;
					
					seq[s]=s;
					
					if(l!=-1)
					mult*=table[seq[l]][seq[s]];
					
					l=s;
					k++;
					if(k>=maxx)
					{ flag=1; break; }
				}
				else
				seq[s]=-1;
				t/=2;
				s++;				
			}
			if(flag==1)
			continue;
			mult*=table[seq[l]][seq[f]];
			seq[s]=seq[f];
			
			s++;
			if(mult>1.01)
			if(k<maxx)
			{
				maxx=k; t=0;
				for(j=0;j<s;j++)
				if(seq[j]!=-1)
				{ finseq[t]=seq[j]; t++; } 
				if(maxx==2)
				break;
			}
		}
		if(finseq[0]==-1)
		cout<<"no arbitrage sequence exists"<<endl;
		else
		for(j=0;j<=maxx;j++)	
		if(j==maxx)
		cout<<finseq[j]+1<<endl;
		else
		cout<<finseq[j]+1<<" ";	
	}
}

plz reply ...thx

[Jan]

Search the board first. Use an exisiting thread.