## 104 - Arbitrage

Moderator: Board moderators

nafi1212
New poster
Posts: 5
Joined: Sat Sep 02, 2006 10:33 pm
Many Many thanx to ImLazy and gits. But, ImLazy, U forgot to remove code.
R u really that lazy??
kbr002
New poster
Posts: 1
Joined: Sun Nov 12, 2006 4:37 am
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
New poster
Posts: 5
Joined: Tue Dec 19, 2006 5:01 pm

### Don't get what's wrong

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
New poster
Posts: 5
Joined: Tue Dec 19, 2006 5:01 pm
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
New poster
Posts: 5
Joined: Tue Dec 19, 2006 5:01 pm
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
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

### 104 Memory Limit Exceeded

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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
The problem lies in the function solve().
The res vector grows beyond capacity.
lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm
oh,you means the default capacity of vector? i will try it.
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Contact:
@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
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
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;
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;
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.
``````
Now I lay me down to sleep...
my profile
cpp_stu2
New poster
Posts: 3
Joined: Sat Aug 11, 2007 5:52 am
Contact:
kwdikosno8
New poster
Posts: 3
Joined: Sat Sep 08, 2007 2:38 am
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?
New poster
Posts: 3
Joined: Sat Aug 02, 2008 11:37 am

### 104....time limit

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