## 103 - Stacking Boxes

**Moderator:** Board moderators

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

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

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

[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

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>>dreturn 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 ( dfor (j=0; j<N; j++)

for (p=N-1; p>=j; p--)

if ( d

*[p] < d**[p+1] ){*

t = dt = d

*[p];*

dd

*[p] = d**[p+1];;*

dd

*[p+1] = t;*

}

}

for (i=0; i<M; i++)

for (j=0; j<M; j++){

if (i!=j && less(i, j) )

map}

}

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

### Please Help P103...

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

Thanks in advance

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

Thanks in advance

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

How DP is used? Can anyone give me an example?

Thanks.

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

See my response in this other post:

http://acm.uva.es/board/viewtopic.php?t=1406

http://acm.uva.es/board/viewtopic.php?t=1406

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

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?

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?

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

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

### WA madness 103

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

Some kind soul, please help me!!

[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

Can anyone tell me what could be wrong???

Some kind soul, please help me!!

[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}

for (j = 0; j < 31; j++)

{

fit

*[j] = 0;*

}

ans}

ans

*= 0;*

containercontainer

*= 0;*

}

container[0] = 0;

for (i = 0; i < n_box; i++)

{

container[i+1] = 1;

for (j = 0; j < n_dim; j++)

{

cin >> boxarr}

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}

}

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{

hold = boxarr

*[k];*

boxarrboxarr

*[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]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]

### 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
kind ppl plz help me

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]
```

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

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