## 103 - Stacking Boxes

Moderator: Board moderators

sathyashrayan
New poster
Posts: 6
Joined: Tue Apr 25, 2006 6:48 pm

### 103, understanding the sample out put (beginner)

Dear group,
I can able to understand the
sample input but not the sample
out put. Can any one help this
beginner?
Thanks for any help

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

Code: Select all

``````MEANING OF SAMPLE OUTPUT #1
5 (5 BOXES)
3 (BOX#3  DIMENSION1=2  DIMENSION2=5  )
1 (BOX#1  DIMENSION1=3  DIMENSION2=7  )
2 (BOX#2  DIMENSION1=8  DIMENSION2=10 )
4 (BOX#4  DIMENSION1=9  DIMENSION2=11 )
5 (BOX#5  DIMENSION1=18 DIMENSION2=21 )
``````
As you can see, all of DIMENSION1 are increasing and all of DIMENSION2 are increasing.

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
Hey !

It ia an old problem .... this bug should be checked before. What a bad type of bug it is. The OJ is accepting the wrong answer when right answers are judged WA . I thibg it is simple LIS problem afte sorting the boxes according to their volume . Why people are not fixing the bug ?
Syed Ishtiaque Ahmed Kallol
CSE,BUET

hedgehog1204
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

### Python program for 103

Here is cute Python code to solve the 103 problem:

Code: Select all

``````# Program that solves the Stacking Boxes problem
# http://acm.uva.es/p/v1/103.html

boxes = []		# list of boxes
nBox = 0		# number of boxes
dim = 0			# dimensions of boxes

# sort boxes by their measurements using bubble sort
def sort_boxes():
for i in range(nBox-1):
for j in range(nBox-i-1):
for k in range(dim):
if boxes[j][k] < boxes[j+1][k]:
break
elif boxes[j][k] > boxes[j+1][k]:
boxes[j], boxes[j+1] = boxes[j+1], boxes[j]
break

file = open('input.txt')
while file:
if line == "":										# exit if end of file
break
vars = line.strip().split(' ')						# get input data from file
nBox, dim = int(vars), int(vars)

boxes = []											# list of boxes
for i in range(nBox):
vars = file.readline().strip().split(' ')		# get input data from file
mes = []										# measurements of a box
for var in vars:
mes.append(int(var))
boxes.append(mes)								# add box to boxes
for box in boxes:									# sort boxes' measurements
box.sort()

oldBoxes = []										# save previous arrangement of boxes
for box in boxes:
oldBoxes.append(box)

sort_boxes()										# sort boxes by their measurements

# Find the longest sring of boxes:
maxBoxes = []										# list that holds the longest nesting string
maxBoxes.append(boxes)							# make it the first box by default
for i in range(nBox-1):								# find the longest string of boxes, try start with box[i]
tempBoxes = []									# temporary boxes that make a string
i1, i2 = i, i+1									# indices of boxes that will be compared
while (i2 < nBox):
nests = True
for j in range(dim):						# check if box[i1] nests in box[i2]
if boxes[i1][j] > boxes[i2][j]:
nests = False
break
if nests:									# if yes - modify tempBoxes and check if it longer then maxBoxes
if tempBoxes == []:
tempBoxes.append(boxes[i1])
tempBoxes.append(boxes[i2])
if len(tempBoxes)>len(maxBoxes):
maxBoxes = tempBoxes
i1, i2 = i2, i2+1						# modify indices accordingly
else:										# if not - try next box
i2 += 1

print len(maxBoxes)									# print output
for box in maxBoxes:
print oldBoxes.index(box)+1,
print
file.close()[
``````

hedgehog1204
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

Code: Select all

``````# Program that solves the Stacking Boxes problem
# http://acm.uva.es/p/v1/103.html

boxes = []
nBox = 0
dim = 0

# sort boxes by their measurements using bubble sort
def sort_boxes():
for i in range(nBox-1):
for j in range(nBox-i-1):
for k in range(dim):
if boxes[j][k] < boxes[j+1][k]:
break
elif boxes[j][k] > boxes[j+1][k]:
boxes[j], boxes[j+1] = boxes[j+1], boxes[j]
break

file = open('input.txt')
while file:
if line == "":
break
vars = line.strip().split(' ')
nBox, dim = int(vars), int(vars)

boxes = []
for i in range(nBox):
mes = []
for var in vars:
mes.append(int(var))
boxes.append(mes)
for box in boxes:
box.sort()

oldBoxes = []
for box in boxes:
oldBoxes.append(box)

sort_boxes()

# Find the longest sring of boxes:
maxBoxes = []
maxBoxes.append(boxes)
for i in range(nBox-1):
tempBoxes = []
i1, i2 = i, i+1
while (i2 < nBox):
nests = True
for j in range(dim):
if boxes[i1][j] > boxes[i2][j]:
nests = False
break
if nests:
if tempBoxes == []:
tempBoxes.append(boxes[i1])
tempBoxes.append(boxes[i2])
if len(tempBoxes)>len(maxBoxes):
maxBoxes = tempBoxes
i1, i2 = i2, i2+1
else:
i2 += 1

print len(maxBoxes)
for box in maxBoxes:
print oldBoxes.index(box)+1,
print
file.close()
``````

Nils
New poster
Posts: 1
Joined: Tue Sep 19, 2006 3:05 am
hedgehog1204: i tried your python script and for the sample input from guitarlover it outputs the wrong answer. I played a bit with your code and here is the part i have changed:
(maybe the indention got messed up)

Code: Select all

``````
# Find the longest sring of boxes:
maxBoxes = []
maxBoxes.append(boxes)
for i in range(nBox-1):
tempBoxes = []
posStack = []
i1, i2 = i, i+1
while (i2 < nBox ):
nests = True
for j in range(dim):
if boxes[i1][j] > boxes[i2][j]:
nests = False
break
if nests:
if tempBoxes == []:
tempBoxes.append(boxes[i1])
posStack.append(i1)
tempBoxes.append(boxes[i2])
posStack.append(i2)
if len(tempBoxes)>len(maxBoxes):
maxBoxes = tempBoxes
i1, i2 = i2, i2+1
else:
if i2 < nBox:
i2 += 1
if not (i2 < nBox):
if len(posStack) < 2:
continue
i2 = posStack.pop() + 1
tempBoxes.pop()
i1 = posStack[len(posStack)-1]
``````

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am
My program outputs the correct answers for the sample input and the input from guitalover but I got a WA Relja
New poster
Posts: 3
Joined: Sat Nov 18, 2006 6:12 pm

### STL sort

I had problem with C++ STL sort()..
When i use it , i got WA , but with bubble sort it's AC..
I overload operators < and = ..What can be wrong?

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:
My program produced correct answers to all the sample inputs, but got a wa. Plz help........

Code: Select all

`````` #include<stdio.h>

struct X{
int arry;
};

int indx, b, n, d, length;
struct X a;

int comp(struct X s1, struct X s2)
{
int i;
for(i=0; i<d; i++)
if(s1.arry[i]>s2.arry[i])
return 1;
else if(s1.arry[i]<s2.arry[i])
return 0;
return 0;
}

int isin(struct X s1, struct X s2)
{
int i;
for(i=0; i<d; i++)
if(s1.arry[i]>=s2.arry[i])
return 0;
return 1;
}

void main()
{
freopen("in.txt", "r", stdin);
int i, k, j, l, bb, res, x, c;
struct X temp;
while(scanf("%d %d", &n, &d)==2)
{
for(i=0; i<n; i++)
{
indx[i]=i;
for(j=0; j<d; j++)
scanf("%d", &a[i].arry[j]);

for(k=0; k<d-1; k++)
for(l=k+1; l<d; l++)
if(a[i].arry[k]>a[i].arry[l])
a[i].arry[k]^=a[i].arry[l]^=a[i].arry[k]^=a[i].arry[l];
}

for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
if(comp(a[i], a[j]))
{
indx[i]^=indx[j]^=indx[i]^=indx[j];
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
for(i=0; i<n; i++)
length[i]=1;
res=1;
x=0;
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
if(isin(a[i], a[j]))
if(length[i]+1>length[j])
{
length[j]=length[i]+1;
if(res<=length[j])
{
res=length[j];
x=j;
}
}
c=res;
bb=1;
b=indx[x];
for(i=x-1; i>=0; i--)
if(length[i]==c-1)
{
b[bb++]=indx[i];
c--;
}
printf("%d\n", res);

for(i=bb-1; i>=0; i--)
printf("%d ", b[i]+1);
puts("");
}
}``````
Is my method wrong? Or I have missed something. Thanks in advance....
form kisui na ... class tai asol....
iF U hv d class u get the form....

kogorman
New poster
Posts: 14
Joined: Sat Dec 02, 2006 6:58 am

### You are not alone, and perhaps help is on the way

You are not alone. This thread started with the same complaint by another. I had it too.

I verified that the above-posted solution indeed:
a: gives the wrong answer sometimes
b: is graded Accepted by the judge.

I have posted a bug in the bugs Forum, and perhaps the moderators will fix it, or at least take the broken judge offline.

In the meanwhile, I would not try to fix your code. It may be correct as it is.
Kevin

kogorman
New poster
Posts: 14
Joined: Sat Dec 02, 2006 6:58 am

### The moderators weigh in

The moderators have replied to my bug. They showed a test case in which my program gave the wrong answer. They seem to agree that there need to be more test cases to prevent broken programs from being accepted, and will probably take care of that soon.

http://online-judge.uva.es/board/viewto ... 4642#54642
Kevin

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:
my program gives:

Code: Select all

``````13
28 7 8 9 10 26 15 11 16 17 19 18 20``````
i think this is also right output........... but why WA??
form kisui na ... class tai asol....
iF U hv d class u get the form....

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:
I am really confuse ... why this code is Wrong?? I cannot find any bag

form kisui na ... class tai asol....
iF U hv d class u get the form....

kernal
New poster
Posts: 1
Joined: Wed May 23, 2007 4:41 am

### 103 - Is This Answer Valid

Hello
I am working on 103 (Stacking Boxes) and am getting Wrong Answers.

I try the test cases and for this input:

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

My output is this:
4
7 2 5 8

however the problem set shows:
4
7 2 5 6

I believe my answer is also correct. Could someone please confirm this for me.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm