103 - Stacking Boxes

[sathyashrayan]

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]

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]

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 ?

[hedgehog1204]

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:
	line = file.readline()								# read line from file
	if line == "":										# exit if end of file
		break
	vars = line.strip().split(' ')						# get input data from file
	nBox, dim = int(vars[0]), int(vars[1])				

	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[0])							# 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]

...and without comments its cuter:

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:
	line = file.readline()								
	if line == "":										
		break
	vars = line.strip().split(' ')						
	nBox, dim = int(vars[0]), int(vars[1])				

	boxes = []											
	for i in range(nBox):
		vars = file.readline().strip().split(' ')		
		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[0])							
	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]

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[0])                     
   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]

My program outputs the correct answers for the sample input and the input from guitalover but I got a WA

[Relja]

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]

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[12];
};

int indx[33], b[33], n, d, length[33];
struct X a[33];

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[0]=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....

[kogorman]

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.

[kogorman]

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.

In the meantime, perhaps looking at the moderators' test case will help you debug your program:
http://online-judge.uva.es/board/viewto ... 4642#54642

[joy]

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??

[joy]

I am really confuse ... why this code is Wrong??
I cannot find any bag

please help......

[kernal]

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]

Search the board first. If you find a thread use it. So, post your problem in an existing thread.