103 - Stacking Boxes

[Tomislav Novak]

Hi!

Could anyone post some critical test data for problem 103, or, even better, send me his AC solution (only binary file), so I could compare outputs?

My code is:
[c]
/* ...spoiler... */
[/c]

Any kind of help is greatly appreciated.

[UFP2161]

Input:

10 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

Output:

1
1

[Tomislav Novak]

I've changed in lns()
[c]
max = 0; maxi = -1;
[/c]
into
[c]
max = 1; maxi = 0;
[/c]
and got accepted now.

Thank you very much UFP2161!

[GreenPenInc]

Heh... I had WA too, then found out that it helps to check the output they want

(I was neglecting the first line of every line pair. Dumb, eh?)

[UrsaMinor]

Here's my Code.
Although I think my program is pretty good and it do get the right answer but it got the TLE....
I want to know why it have a TLE and what should I do?
Thank you.

[pascal]
{UVA 103.pas}
{Stacking Boxes}
type
TypeOfBox=record
d:array[1..11] of integer;
next:integer;
f:integer;
end;
var
box :array[1..31] of TypeOfBox;
ans :array[1..31] of integer;
i,j,n,k,p :integer;
max,s :longint;

function check(inner,outer:integer):boolean; {To Check if Box[inner] can be put into Box[outer]}
var p:boolean;
i:integer;
begin
p:=true;
for i:=1 to n do if box[inner].d>box[outer].d then p:=false;
check:=p;
end;

Procedure sort(id:integer); {To Sort D of each box}
var
i,j,t,min :integer;
begin
for i:=1 to n-1 do begin
min:=i;
for j:=i+1 to n do if box[id].d[min]>box[id].d[j] then min:=j;
t:=box[id].d;
box[id].d:=box[id].d[min];
box[id].d[min]:=t;
end;
end;

begin
while not eof do begin
fillchar(box,sizeof(box),0);
readln(k,n);
for i:=1 to k do begin
for j:=1 to n do
read(box.d[j]);
readln;
sort(i);
end;
for i:=1 to k do begin
max:=0;p:=0;
for j:=1 to k do if j<>i then begin
if check(j,i) and (max<=box[j].f) then begin
p:=j;
max:=box[j].f;
end;
end;
if p<>0 then begin
box.f:=max+1;
box.next:=p;
end;
end;
max:=0;
for i:=1 to k do if box.f>max then begin max:=box.f;p:=i;end;
writeln(max+1);
s:=1;
ans[s]:=p;
while box[p].f<>0 do begin
inc(s);
ans[s]:=box[p].next;
p:=box[p].next;
end;
for i:=s downto 2 do write(ans[i],' ');
writeln(ans[1]);
end;
end.
[/pascal]

[UrsaMinor]

I changed the Sort Procedure to QSort But Still TLE.............

[pascal]{UVA 103.pas}
{Stacking Boxes}
type
TypeOfBox=record
d:array[1..11] of integer;
next:integer;
f:integer;
end;
var
box :array[1..31] of TypeOfBox;
ans :array[1..31] of integer;
i,j,n,k,p :integer;
max,s :longint;

function check(inner,outer:integer):boolean;
var p:boolean;
i:integer;
begin
p:=true;
for i:=1 to n do if box[inner].d>box[outer].d then p:=false;
check:=p;
end;

procedure QSort(id: Integer);

procedure Sort(l, r: Integer);
var
i, j ,x ,y : integer;
begin
i := l; j := r; x := box[id].d[(l+r) DIV 2];
repeat
while box[id].d < x do i := i + 1;
while x < box[id].d[j] do j := j - 1;
if i <= j then
begin
y := box[id].d; box[id].d := box[id].d[j]; box[id].d[j] := y;
i := i + 1; j := j - 1;
end;
until i > j;
if l < j then Sort(l, j);
if i < r then Sort(i, r);
end;

begin {QuickSort};
Sort(1,n);
end;


begin
while not eof do begin
fillchar(box,sizeof(box),0);
readln(k,n);
for i:=1 to k do begin
for j:=1 to n do
read(box.d[j]);
readln;
Qsort(i);
end;
for i:=1 to k do begin
max:=0;p:=0;
for j:=1 to k do if j<>i then begin
if check(j,i) and (max<=box[j].f) then begin
p:=j;
max:=box[j].f;
end;
end;
if p<>0 then begin
box.f:=max+1;
box.next:=p;
end;
end;
max:=0;
for i:=1 to k do if box.f>max then begin max:=box.f;p:=i;end;
writeln(max+1);
s:=1;
ans[s]:=p;
while box[p].f<>0 do begin
inc(s);
ans[s]:=box[p].next;
p:=box[p].next;
end;
for i:=s downto 2 do write(ans[i],' ');
writeln(ans[1]);
end;
end.




[/pascal]

[wipper]

Always "Wrong Answer". I don't understand why. Can anybody help me?
[cpp]
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <string.h>

#define MAX_K 30
#define MAX_N 10

char s[65535];
int k,n,i,j,max,e;
int a[MAX_K][MAX_N],b[MAX_K][MAX_K],c[MAX_K],d[MAX_K],o[MAX_K];

void rearrange(int x);
void sort2(int x,int y);
int nested(int x,int y);

int main(void)
{
#ifndef ONLINE_JUDGE
close(0); open("input.txt",O_RDONLY);
close(1); open("output.txt",O_WRONLY|O_CREAT,0600);
#endif

strcpy(s,"");
gets(s);
while(strcmp(s,"")!=0)
{
sscanf(s,"%d %d",&k,&n);
for(i=0;i<k;i++)
{
for(j=0;j<n;j++)
scanf("%d",&a[j]);
o=i;
rearrange(i);
}
gets(s);
for(i=0;i<k;i++)
for(j=1;j<k;j++)
sort2(j-1,j);
for(i=0;i<k;i++)
for(j=0;j<k;j++)
b[j]=nested(i,j);
for(i=0;i<k;i++)
{
c=0;
d=0;
}
max=0;
for(i=0;i<k;i++)
for(j=0;j<k;j++)
if(b[j]==1 && c[j]+1>c)
{
c=c[j]+1;
d=j;
if(max<c)
{
max=c[i];
e=i;
}
}
j=e;
for(i=0;i<=max;i++)
{
c[i]=o[j]+1;
j=d[j];
}
printf("%d\n",max+1);
for(i=max;i>0;--i)
printf("%d ",c[i]);
printf("%d\n",c[0]);

strcpy(s,"");
gets(s);
}

return 0;
}

void rearrange(int x)
{
int i,j,t;

for(i=0;i<n;i++)
for(j=1;j<n;j++)
if(a[x][j-1]<a[x][j])
{
t=a[x][j-1];
a[x][j-1]=a[x][j];
a[x][j]=t;
}
return;
}

void sort2(int x,int y)
{
int i,j,t;

for(i=0;i<n;i++)
{
if(a[x][i]==a[y][i])
continue;
if(a[x][i]>a[y][i])
{
for(j=0;j<n;j++)
{
t=a[x][j];
a[x][j]=a[y][j];
a[y][j]=t;
}
t=o[x];
o[x]=o[y];
o[y]=t;
}
break;
}
return;
}

int nested(int x,int y)
{
int i;

for(i=0;i<n;i++)
if(a[x][i]<=a[y][i])
return 0;
return 1;
}
[/cpp]

[hiloshi]

hi wipper.

Your program is almost always correct, but maybe have a bit bug.

Try following case(X):

Code: Select all

3 3
1 1 1
1 2 2
1 3 3

Your output is 1, and it is correct.

But try following another case(Y):

Code: Select all

5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9
5 3
1 2 3
2 3 4
3 4 5
4 5 6
6 7 8
3 3
1 1 1
1 2 2
1 3 3

Your output is follow:

Code: Select all

5
3 1 2 4 5
4
7 2 5 6
5
1 2 3 4 5
1
5

The last data set in case Y is same as the data set in case X.
But your output is different.

Check your initialize method or output method.
There is maybe a bit bug, it confuses you.

[hoigy]

this is my code using an approch of recurion and exhauction on this problem
but it got a TLE is test case 5
however,i have tried the case of 30 10 in my own computer which can run within 0.1 sec.
please help me...
[cpp]#include <iostream>
using namespace std;
/*
if there exist no box
update list
else
for remining box
get the smallest id one from supply list
delete geted id
if it can be insert
insert it in another list
recur;
delete the id box from list
else
update list;
*/
int r(int K,int N,bool E[],int T,int PreviousList[],int& Max,int* pList,int A[][10]);
int r(int K,int N,bool E[],int T,int PreviousList[],int& Max,int* pList,int A[][10])
{
bool Exist[30];
int Total=T;
int List[30];
bool tempB=true;
bool Inserted;
bool tempB1,tempB2;
int count=0;
for (int i=0;i<=K-1;i++)
{
Exist=E;
List=PreviousList;
if (E)
{
tempB=false;
count++;
}
}
if (tempB)
{
if (Total>Max)
{
Max=Total;
for (int i=0;i<=Total-1;i++)
*(pList+i)=List;
}
}
else if (Max<K && Total+count>Max)
{
for (int i=0;i<=K-1;i++)
if (Exist)
{
Inserted=false;
for (int j=0;j<=Total;j++)
{
tempB1=true;
tempB2=true;
for (int k=0;k<=N-1;k++)
{
if (j<Total)
if (A[k]>=A[List[j]][k])
tempB1=false;
if (j>0)
if (A[k]<=A[List[j-1]][k])
tempB2=false;
}
if (tempB1 && tempB2)
{
for (int k=Total-1;k>=j;k--)
List[k+1]=List[k];
List[j]=i;
Total++;
Inserted=true;
Exist=false;
r(K,N,Exist,Total,List,Max,pList,A);
for (int k=0;k<=Total-1;k++)
if (List[k]==i)
{
for (int l=k;l<=Total-1;l++)
List[l]=List[l+1];
k=Total-1;
}
Total--;
j=Total;
}
}
if (!Inserted)
{
if (Total>Max)
{
Max=Total;
for (int j=0;j<=Total-1;j++)
*(pList+j)=List[j];
}
}
}
}
return 0;
}

int main()
{
int K,N,tempI;
int A[30][10];
int Max;
int List[30];
bool Exist[30];

while (cin >> K >> N)
{
Max=0;
for (int i=0;i<=K-1;i++)
{
Exist[i]=true;
List[i]=0;
for (int j=0;j<=N-1;j++)
cin >> A[i][j];
}

for (int i=0;i<=K-1;i++)
for (int j=0;j<=N-2;j++)
for (int k=j+1;k<=N-1;k++)
if (A[i][j]>A[i][k])
{
tempI=A[i][j];
A[i][j]=A[i][k];
A[i][k]=tempI;
}

r(K,N,Exist,0,List,Max,List,A);

cout << Max << endl;
cout << List[0]+1;
for (int i=1;i<=Max-1;i++)
cout << " " << List[i]+1;
cout << endl;
}
return 0;
}[/cpp]

[wirjawan]

[cpp]
for (int i=0;i<=K-1;i++)
for (int j=0;j<=N-2;j++)
for (int k=j+1;k<=N-1;k++)
if (A[j]>A[k])
{
tempI=A[j];
A[j]=A[k];
A[k]=tempI;
}
[/cpp]

this is slow.. around O(n^2) bubble * n times = O(n^3), you might want to consider using a faster sorting alrgorithm (qsort in C, or sort in C++ STL) after you are done with sorting. you can apply modified LIS (Longest Increasing Subsequence), instead of comparing a number you will be comparing a whole chunk of numbers ( one row of matrix with another ).

hope this helps =)

[hoigy]

I think you are correct.
On the other hand,I know why I can run my program in my own computer but not the judge
This is because the judge is only Pentium III - 800 MHz ...while my computer is AMD 2400+
Thank you for your idea anyway.

[eg_frx]

Guess you may use the STL function sort.

[hoigy]

Guess you may use the STL function sort.

what is the STL function sort?

[wirjawan]

http://www.sgi.com/tech/stl/sort.html

[XQuest]

thanks, hiloshi

Got an AC after using your test cases and changed some of my code. I guess the problem with wipper and I is that we forgot to consider the case where the longest nesting string length is 1.