## 103 - Stacking Boxes

Moderator: Board moderators

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

I think that there are no tricky inputs in this task ( but I may be wrong )
If you didn't get your program AC look at this:

1. Check your program for test cases where k=1 or all the boxes are the same size...

2. Look carefully the next value shold be less ( not equal or less )
3. Look again at sorting -- while I was writin that program I had a small mistake there..
4. Check if you didn't forget about some boxes...

If your program is still WA. Send me the code on e-mail or write it in the post..

Good Luck

mindae
New poster
Posts: 8
Joined: Sun May 19, 2002 8:58 pm
Contact:

### 103.. i can't understand that why judge result is W/A;;

How this problem solve?
dynamic ?
hmm

sorry but I want large input data and output data.

my i/o data;

[input]
10 10
1 2 3 4 5 6 7 8 9 10
4 5 2 3 3 5 6 7 9 10
20 30 2 1 3 4 5 6 9 10
1 2 3 4 5 6 7 8 9 10
5 2 3 4 5 6 9 10 22 30
2 3 4 5 6 7 8 9 10 11
2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10 11 12
98 23 43 53 23 43 53 10 4 90
1 1 1 2 3 4 5 9 10 11

[output]
4
1 7 8 9
+_+ o bba sal sal

vivid
New poster
Posts: 6
Joined: Tue Jul 16, 2002 6:31 pm
Algorithm solving was described some posts earlier. I've solved the task in the same way but i get WA. It passes all test i've found on this forum. What is wrong with it?
[cpp]
#include <iostream.h>
#include <string.h>

int d[31][10];
int map[30][30];

int N, M;

char less(int i, int j)
{
for (int k=0; k<N; k++)
if ( d[k]>=d[j][k] )
return 0;
return 1;
}

char equal(int i, int j)
{
for (int k=0; k<N; k++)
if ( d[k]!=d[j][k] )
return 0;
return 1;
}

int ml;
int mp[30];

int len[30];

int main()
{
int i, j, k, t, p;

while (cin>>M){
cin>>N;

for (i=0; i<M; i++){
for (j=0; j<N; j++)
cin>>d[j];
for (j=0; j<N; j++)
for (p=N-1; p>=j; p--)
if ( d[p] < d[p+1] ){
t = d[p];
d[p] = d[p+1];;
d[p+1] = t;
}
}

for (i=0; i<M; i++)
for (j=0; j<M; j++){
if (i!=j && less(i, j) )
map[j] = 1;
else
map[i][j] = 0;
}
ml=0;

for (int s=0; s<M; s++){
memset(len, 0, sizeof(len));
char found = 1;
len[s]=1;
while (found){
found = 0;
for (i=0; i<M; i++)
if (len[i]){
for (j=0; j<M; j++)
if (map[i][j] && len[j]<len[i]+map[i][j]){
len[j] = len[i]+map[i][j];
found = 1;
}
}
}
int l=0;
for (i=0; i<M; i++)
if (len[i]>len[l])
l=i;
int ll =len[l];
if (ll>ml){
ml=ll;
int prev = l;
i=ll;
mp[--i]=l;

for (; i>0;)
for (j=0; j<M; j++)
if (map[j][prev] && len[j]==len[prev]-map[j][prev] ){
mp[--i]=j;
prev = j;
break;
}
}
}
cout<<ml<<endl;
for (i=0; i<ml; i++)
cout<<mp[i]+1<<" ";
cout<<endl;
}
return 0;
}
[/cpp]

mindae
New poster
Posts: 8
Joined: Sun May 19, 2002 8:58 pm
Contact:

### ;)

thx;
but i already passed 103 problem..
solution is DFS ^0^
+_+ o bba sal sal

16023
New poster
Posts: 4
Joined: Sat Sep 21, 2002 7:39 am

Hi,
I try to solve this problem in these steps:
1) sort the numbers for each row
2) find the longest path

I know how to do the first step, but I have no clue how to achieve the second step. In my mind, i think i need to use DFS...but how? How can I connect the arrays (assume i am using two dimensional arrays to hold the numbers) to look like a graph??

16023
New poster
Posts: 4
Joined: Sat Sep 21, 2002 7:39 am

### prob 103 - dynamic programming

To solve problem 103, some people said on the board about DP (Dynamic Programming).
How DP is used? Can anyone give me an example?
Thanks.

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
Here's a general idea of this problem:

1) The order of the dimensions isn't important, so feel free to sort the dimensions of the box as you read it in. Since the dimensionality doesn't exceed 10, insert sorting is an easy to use method.

2) I sorted my boxes also, based on the first dimension (after the dimensions for each box had been sorted). The only problem with this, is that you need to also keep track of the order the boxes were originally read in. I kept track of the order as an extra dimension, one that would not be compared when determining nesting ability.

3) Now that everything's sorted, DP comes into play. Need to find the longest string of nesting boxes.

You could try to find all the various combinations and brute force your way to a solution. But that's ugly. You don't want to go there. Instead, with DP, you gradually build the solution. With each box, you're not sure yet whether it is in the longest string, but you can determine the longest string involving that box up to that point, and you can determine the previous box in that list. I'll step you through how I chose to implement DP in my program.

For the first box in the sorted list, you know the length is 1, and there can't be any boxes that it nests into. (I sorted the boxes in descending order, you'll see why later) For box #2, you need to determine whether it can nest into box 1. If it can, the length at box #2 is 2, and box #1 is the end of the list, prior to adding box #2. For box #3, determine whether it can nest into box #2. If it can, add one to the length found for box#2, and consider box #2 the previous box. Whether it can or not, check box#1 and see if it can nest. If it can, does adding one to the length for box #1 give a longer length for box #3? If it does, store the new length and the new previous box. Etc.

Yes, this is still at the trivial level. There is some room for improving this algorithm. You can stop checking whether smaller boxes nest once the length for the sequence up to the current box is greater than the box number. So, if you're at box 20, and you've found that there is a length of at least 16 boxes that nest, including box 20, then you don't need to check boxes 15 and below, since they could not give you a longer nesting length.

Now, how do you reconstruct the longest list? I first did a scan through the list to find the longest overall length. With the boxes sorted in descending order, take one of the boxes that claims the longest overall length, output the length, output the read-in-order number of the box with the longest overall length (remember, the boxes were sorted in descending order, so as we worked our way through, the largest box is at the "start" of the list, the smallest is at the "end" of the list, and we're going to print the list in order, starting at the "end" and moving to the "start"). From there, find the previous box, and output it's read-in-order number, etc until there is no previous box.

So that's DP: instead of trying to enumerate all the possible cominations and determine which is the best, it determines at each step, what is the best possible solution up to that point. You must be able to determine a base case(s), and from that base case(s), a way to gradually build a solution. DP is generally used in "longest string" type cases.

David

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
See my response in this other post:
http://acm.uva.es/board/viewtopic.php?t=1406

16023
New poster
Posts: 4
Joined: Sat Sep 21, 2002 7:39 am
Thanks, David!

Boffin
New poster
Posts: 2
Joined: Mon Sep 30, 2002 8:50 pm
Location: Israel
Contact:

### 103 problem....

Hi.
I didn't clearly understand the problem.

For example: if I have box D={1,2,3,4,5}
Can I rearrange it D={1,3,5,2,4} or I have to keep order of dimensions?

I mean only
{2,3,4,5,1}
{3,4,5,1,2}
{4,5,1,2,3}
{5,1,2,3,4}
rearrangements are available?

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
I believe { 1, 4, 3, 5, 2 } is valid, ... the problem statement doesn't limit the rearrangement to rotate only.

-turuthok-

21743NX
New poster
Posts: 9
Joined: Tue Aug 27, 2002 8:39 am

### Hi, can some kind soul give me some more test input??

can anybody give me some test inputs for this question??

21743NX
New poster
Posts: 9
Joined: Tue Aug 27, 2002 8:39 am

Hi, i seemed to get all the test inputs (including those in the forum) correct. Yet, I kept getting the W.A
Can anyone tell me what could be wrong???

[cpp]
#include <iostream.h>

int n_dim, max_level;
int fit[30][30];
int ans[31];
int container[31];
int maxi(int ,int);

int main(void)
{
int n_box;
int i, j, k;
int c;
int hold, test;

int boxarr[30][10];

while (cin >> n_box >> n_dim)
{
for (i = 0; i < 30; i++)
{
for (j = 0; j < 10; j++)
{
boxarr[j] = 0;
}

for (j = 0; j < 31; j++)
{
fit[j] = 0;
}
ans = 0;
container = 0;
}

container[0] = 0;
for (i = 0; i < n_box; i++)
{
container[i+1] = 1;
for (j = 0; j < n_dim; j++)
{
cin >> boxarr[j];
}
}

for (i = 0; i < n_box; i++)
{
for (j = 0; j < (n_dim-1); j++)
{
for (k = 0; k < (n_dim-1); k++)
{
if (boxarr[k] > boxarr[k+1])
{
hold = boxarr[k];
boxarr[k] = boxarr[k+1];
boxarr[i][k+1] = hold;
}
}
}
}

for (k = 0; k < n_box; k++)
{
c = 0;
for (j = 0; j < n_box; j++)
{
test = 1;
for (i = 0; i < n_dim; i++)
{
if (boxarr[k][i] >= boxarr[j][i])
{
test = 0;
break;
}
}

if (test == 1)
{
fit[k][c] = (j+1);
c++;
}
}
}

max_level = 0;

for (i = 0; i < n_box; i++)
{
maxi(i, 0);
}

cout << max_level << endl;

for(i = 1; i <= max_level; i++)
{
cout << ans[i] << " ";
}
cout << endl;

}
return 0;
}

int maxi(int i, int level)
{

int kk, k, test;
int temp;

level++;

if (fit[i][0] == 0)
{
if (level > max_level)
{
max_level = level;

ans[level] = (i+1);
return 1;
}
return 0;
}
else
{
temp = 0;
for (kk = 0; kk < n_dim; kk++)
{
test = 0;
k = fit[i][kk];

if (k == 0)
{
break;
}

if(container[k] == 1)
{
container[k] = 0;
test = maxi(k-1, level);
container[k] = 1;
}
else
{continue;}

if (test == 1)
{
temp = 1;
ans[level] = i + 1;
}
}
}

if (temp == 1)
{
return 1;
}
else
{
return 0;
}
}

[/cpp]

off_algos
New poster
Posts: 29
Joined: Wed Nov 13, 2002 11:37 am
Location: india

### 103 WA!!

in problem 103
i use the following algorithm
first i sort the dimensions of all the boxes
then i sort the boxes into lexicographic order depending on their dimensions
finally i use DP method
(similar to that used to find the longest monotonic subsequence)
and write the output
can u help me why i get WA
sorry for the length of the code

Code: Select all

``````[cpp]

#include <stdio.h>
int *boxno,t;
void pr(int a[],int upos)
{
if(a[upos]==-1)
{
if(upos==t)
printf("%d\n",boxno[upos]);
else
printf("%d ",boxno[upos]);
}
else
{
pr(a,a[upos]);
if(upos==t)
printf("%d\n",boxno[upos]);
else
printf("%d ",boxno[upos]);
}
}
int main()
{
int nbox,ndim;
while(scanf("%d%d",&nbox,&ndim)>0)
{
int **b=new int*[nbox];
boxno=new int[nbox];
for(int i=0;i<nbox;i++)
{
b[i]=new int[ndim];
boxno[i]=i+1;
}
for(int i=0;i<nbox;i++)
for(int j=0;j<ndim;j++)
{
scanf("%d",&b[i][j]);
}
for(int i=0;i<nbox;i++)
{
for(int j=0;j<ndim;j++)
for(int k=0;k<ndim-j-1;k++)
{
if(b[i][k]>b[i][k+1])
{
int tp=b[i][k];
b[i][k]=b[i][k+1];
b[i][k+1]=tp;
}
}
}
for(int i=ndim-1;i>=0;i--)
{
for(int j=0;j<nbox;j++)
for(int k=0;k<nbox-1-j;k++)
{
if(b[k][i]>b[k+1][i])
{
int *tp=b[k];
b[k]=b[k+1];
b[k+1]=tp;
int temp=boxno[k];
boxno[k]=boxno[k+1];
boxno[k+1]=temp;
}
}
}
int *nb=new int[nbox],*prev=new int[nbox];
nb[0]=1;
prev[0]=-1;
for(int i=1;i<nbox;i++)
{
int max=1,pre=-1;
for(int j=i-1;j>=0;j--)
{
int k;
for(k=0;k<ndim;k++)
{
if(b[i][k]>=b[j][k])
{
}
else
break;
}
if(k==ndim)
{
if(nb[j]+1>max)
{
max=nb[j]+1;
pre=j;
}
}
}
nb[i]=max;
prev[i]=pre;
}
/*for(int i=0;i<nbox;i++)
{
printf("%d ",boxno[i]);
for(int j=0;j<ndim;j++)
{
printf("%d ",b[i][j]);
}
printf("\n");
}*/
int max=nb[0],upos=0;
for(int i=1;i<nbox;i++)
{
if(nb[i]>=max)
{
max=nb[i];
upos=i;
}
}
printf("%d\n",max);
t=upos;
pr(prev,upos);
delete []nb,delete []prev,delete []boxno;
for(int i=0;i<nbox;i++)
delete []b[i];
delete []b;
}
return 0;
}
[/cpp]``````
kind ppl plz help me

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
i think your algo is wrong... it's a bit suspicious to sort the strings in lexicographic order....

sorting the dimensions of each cube is good, to see whether a box fits in another.

i just got accepted, my algo is:

build a N*N table like this:
tab[i,j] = 1 iff box i fits in box j
find longer path in the oriented graph described by this table... it's easy with recursion.
general rule:
if two boxes b1 b2 fit in box B, the longer path from B is max(b1,b2)+1
i'm not very clear sorry...

this two step attack should get this problem down in a few milliseconds

<-- who said i was kind? this is me in 9 2000 ... i look ugly and i'm a full time loser now
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli