103 - Stacking Boxes

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

103 (Stacking Boxes) - WA

Post by 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. ;)
Last edited by Tomislav Novak on Sat May 29, 2004 12:34 pm, edited 1 time in total.
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by 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
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

Post by 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
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc »

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

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

"Finally I have freed myself from the clutches of the garbage fairy!"
UrsaMinor
New poster
Posts: 2
Joined: Thu Sep 02, 2004 3:46 pm
Location: China

103 TLE

Post by 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
New poster
Posts: 2
Joined: Thu Sep 02, 2004 3:46 pm
Location: China

Post by 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
New poster
Posts: 1
Joined: Sat Aug 28, 2004 11:16 pm

103 - WA ???

Post by 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
New poster
Posts: 20
Joined: Fri Aug 27, 2004 8:15 am
Location: Kanagawa, Japan

Post by 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.
I hope you can understand my poor English.
hoigy
New poster
Posts: 3
Joined: Mon Nov 01, 2004 6:34 pm

103 TLE

Post by 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
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia

Post by 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
New poster
Posts: 3
Joined: Mon Nov 01, 2004 6:34 pm

Post by 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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

Post by eg_frx »

Guess you may use the STL function sort.
hoigy
New poster
Posts: 3
Joined: Mon Nov 01, 2004 6:34 pm

Post by hoigy »

eg_frx wrote:Guess you may use the STL function sort.
what is the STL function sort?
wirjawan
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia

Post by wirjawan »

..
XQuest
New poster
Posts: 1
Joined: Thu Dec 30, 2004 10:20 am

Post by 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. :)
the quest for the light ...
Post Reply

Return to “Volume 1 (100-199)”