Posted: Thu Nov 09, 2006 9:01 pm
Many Many thanx to ImLazy and gits. But, ImLazy, U forgot to remove code.
R u really that lazy??
R u really that lazy??
Code: Select all
#define T(_I, _J) table[_I+(_J<<5)]
...
double table[32<<5];
Page 14 of 15
Posted: Fri Nov 17, 2006 12:52 pm
I do not quite understand this:
Could somebody explain it?
Don't get what's wrong
Posted: Tue Dec 19, 2006 5:14 pm
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
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;
}
Posted: Wed Dec 20, 2006 11:13 am
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
Thanks to all who had tried to debug
Posted: Wed Dec 20, 2006 12:12 pm
1 more test case here in case you made the same logic error as me
Input:
Output:
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
Code: Select all
1 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
104 Memory Limit Exceeded
Posted: Sun Apr 01, 2007 3:50 pm
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;
}
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;
}
Posted: Mon Apr 02, 2007 12:34 pm
The problem lies in the function solve().
The res vector grows beyond capacity.
The res vector grows beyond capacity.
Posted: Mon Apr 02, 2007 5:18 pm
oh,you means the default capacity of vector? i will try it.
Posted: Tue Apr 03, 2007 2:27 pm
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.
Posted: Sat Apr 07, 2007 7:28 pm
@gits:
I got AC, but I have this doubt.
I feel the above statement should be:-
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?
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]But why is it not required? Why is just calculating for m=1 enough?
Posted: Mon Aug 13, 2007 3:49 pm
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...
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.
Posted: Tue Aug 14, 2007 5:15 pm
Posted: Sun Sep 09, 2007 3:01 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?
can someone explain me step by step how can u find the coplexity?
104....time limit
Posted: Sat Aug 30, 2008 11:56 pm
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
plz reply ...thx
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
Re: 104....time limit
Posted: Sun Sep 07, 2008 10:52 am
Search the board first. Use an exisiting thread.