103 - Stacking Boxes
Moderator: Board moderators
-
- 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
I can able to understand the
sample input but not the sample
out put. Can any one help this
beginner?
Thanks for any help
Hi,
As you can see, all of DIMENSION1 are increasing and all of DIMENSION2 are increasing.
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 )
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 ?
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
CSE,BUET
Bangladesh
-
- 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:
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()[
-
- New poster
- Posts: 13
- Joined: Sat Oct 04, 2003 12:03 am
- Location: USA
- Contact:
...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()
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)
(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]
My program produced correct answers to all the sample inputs, but got a wa. Plz help........
Is my method wrong? Or I have missed something. Thanks in advance....
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("");
}
}
form kisui na ... class tai asol....
iF U hv d class u get the form....
iF U hv d class u get the form....
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.
![:D](./images/smilies/icon_biggrin.gif)
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
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.
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
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
my program gives:
i think this is also right output........... but why WA??
Code: Select all
13
28 7 8 9 10 26 15 11 16 17 19 18 20
form kisui na ... class tai asol....
iF U hv d class u get the form....
iF U hv d class u get the form....
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.
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.
Search the board first. If you find a thread use it. So, post your problem in an existing thread.
Ami ekhono shopno dekhi...
HomePage
HomePage