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

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

103, understanding the sample out put (beginner)

Post by sathyashrayan » Sat Jul 08, 2006 9:26 pm

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
Location: TORONTO, CANADA

Post by daveon » Tue Jul 11, 2006 3:28 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.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Tue Aug 01, 2006 2:05 pm

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
Bangladesh

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

Python program for 103

Post by hedgehog1204 » Sun Aug 20, 2006 12:24 pm

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
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

Post by hedgehog1204 » Sun Aug 20, 2006 12:28 pm

...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
New poster
Posts: 1
Joined: Tue Sep 19, 2006 3:05 am

Post by Nils » Tue Sep 19, 2006 4:52 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[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
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu » Mon Oct 02, 2006 11:30 am

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

Relja
New poster
Posts: 3
Joined: Sat Nov 18, 2006 6:12 pm

STL sort

Post by Relja » Sat Nov 18, 2006 6:16 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by joy » Sat Dec 02, 2006 12:40 pm

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

Post by kogorman » Sat Dec 02, 2006 8:43 pm

You are not alone. :D 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

Post by kogorman » Sat Dec 02, 2006 9:04 pm

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
Kevin

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

Post by joy » Sat Dec 02, 2006 9:15 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by joy » Sat Dec 23, 2006 10:45 am

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

please help......
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

Post by kernal » Wed May 23, 2007 4:50 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed May 23, 2007 8:38 pm

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

Post Reply

Return to “Volume 1 (100-199)”