103 - Stacking Boxes

[capella]

i use DP. i can't figure out what test case can make it get WA. can anyone help me? sincerely thanks!
[cpp]
#include<iostream>
#include<string.h>
using namespace std;

unsigned long box[30][10]; //stores the size of each box
int arrbox[10]; //the i'th smallest box is of index arrbox comparing the first dimension after the dimenstions are sorted
int n,dim;
int chain[30][2]; //chain[1] is the length of the longest chain starting from the i'th smallest box
//chain[0] is the next box if going along the longest chain

void bubble(int k){
//sorts the k'th box's dimensions in descending order
for(int i=0;i<dim-1;i++)
for(int j=0;j<dim-1-i;j++)
if(box[k][j+1]>box[k][j]){
unsigned long temp=box[k][j+1];
box[k][j+1]=box[k][j],box[k][j]=temp;
}
}

int larger(int i,int k){
//judge whether the k'th smallest box can be fixed in the i'th smallest box
for(int j=0;j<dim;j++)
if(box[arrbox][j]<=box[arrbox[k]][j])
return 0;
return 1;
}

void getchain(int k){
//starting from the k'th smallest box, find chain[k][0](the next box) and chain[k][1](the longest length starting from it)
if(chain[k][1]!=-1)
return;
chain[k][1]=1;
for(int i=k+1;i<n;i++)
if(larger(i,k)){
getchain(i);
if(chain[1]+1>chain[k][1])
chain[k][1]=chain[1]+1,chain[k][0]=i;
}
}

void arrangebox(){
//sort the boxes in ascending order
int i,j;
for(i=0;i<n;i++)
arrbox=i;
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
if(box[arrbox[j+1]][0]<box[arrbox[j]][0]){
int temp=arrbox[j+1];
arrbox[j+1]=arrbox[j],arrbox[j]=temp;
}
}

void main(){
int i;
while(cin>>n>>dim){
memset(chain,-1,sizeof(chain));
for(i=0;i<n;i++)
for(int j=0;j<dim;j++)
cin>>box[j];

for(i=0;i<n;i++)
bubble(i);

arrangebox();

for(i=0;i<n;i++)
getchain(i);
if(n>0){
int start=0;
for(i=1;i<n;i++)
if(chain[1]>chain[start][1])
start=i;

cout<<chain[start][1]<<endl;
while(chain[start][0]!=-1){
cout<<arrbox[start]+1<<' ';
start=chain[start][0];
}
cout<<arrbox[start]+1<<endl;
}
else
cout<<0<<endl;
}
}[/cpp]

[Ryan Pai]

Try the case where there are two boxes of the same size (they should not be able to fit in one another).

[SilVer DirectXer]

then ...
how about yr case2
when the dimension is negative?

how do u process it?

[George]

Hello,

I have created an algorithm that reads the input and stores it in a 30x10 table, then short the dimensions and then short the boxes. However it seams that some boxes have to be removed that does not match, but this doesn't seam to work fine. Here is the C++ program:

[cpp]#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

int k; //Number of boxes
int n; //Dimensionality
int d[30][10]; //Dimension length [box_number][dimension_number]
int o[30]; //Original order numbers
int ReadInputSuccess; //1 if reading data was successful, otherwise 0

void ReadInput()
{
if (scanf("%d %d", &k, &n) != 2)
{
ReadInputSuccess = 0;
return; //Exit if there are no input data
}
int i,j; //Counters
for (i=0; i<k; i++) //i=box number counter
for (j=0; j<n; j++) //j=dimensions counter
scanf("%d", &d[j]);
//Setup original order
for (i=0; i<k; i++)
o=i;
//Success
ReadInputSuccess=1;
}

void ShortDimensions()
{
//Short dimensions is boxes
int i,j,l; //Counters
//Vars used in shorting
int MinValue;
int PosForMinValue;
int t; //Temp for swapping
for (i=0; i<k; i++)
{
//Short numbers in d
for (j=0; j<n; j++)
{
MinValue=d[j];
PosForMinValue=j;
for (l=j; l<n; l++)
{
if (MinValue>d[l])
{
MinValue=d[l];
PosForMinValue=l;
}
}
//Swap d[PosForMinValue],d[j]
t=d[PosForMinValue];
d[PosForMinValue]=d[i][j];
d[i][j]=t;
}
}
}

int CompareBoxes(int Box1No, int Box2No)
{
//Compares all the dimensions of two boxes
//Parameters: the Numbers of 2 boxes in d[box_no]
//Returns 1 if the Box2 < Box1
//otherwise 0
int i;
//This will find a dimension that is not equal for both boxes
for (i=0; (i<n) && (d[Box1No][i]==d[Box2No][i]); i++);
//return the result by comparing a dimension that is not same
return ((d[Box1No][i]>d[Box2No][i])?1:0);
}

void SwapBoxes(int b1, int b2)
{
//Shap two boxes
//and setup original order
int t; //Temp for swapping
//swap original order first
t=o[b1];
o[b1]=o[b2];
o[b2]=t;
int i; //Counter
for (i=0; i<n; i++)
{
t=d[b1][i];
d[b1][i]=d[b2][i];
d[b2][i]=t;
}
}

void ShortBoxes()
{
//This will short all boxes
int i,j; //Counters
int MinBoxPos; //Position for the minimum box
for (i=0; i<k; i++)
{
//This will short the boxes
MinBoxPos=i;
for (j=i; j<k; j++)
{
if (CompareBoxes(MinBoxPos, j) == 1)
{
MinBoxPos=j;
}
}
//Swap
SwapBoxes(MinBoxPos, i);
}
}

void RemoveUnwantedBoxes()
{
//This will remove boxes that have at least 1 dimension that does not match
//This will change o[number]=Unwated_Box_Num to o[number]=-1
int i,j; //Counters
int bMatches; //Flag, 0=no, 1=yes
for (i=0; i<k-1; i++)
{
//Check if the box has been erased
if (o[i]>=0)
{
//Check if box d[i] matches with the next one (d[i+1])
bMatches=1;
for (j=0; (j<n) && (bMatches==1); j++)
{
if (d[i][j]>d[i+1][j])
{
bMatches=0;
}
}
if (bMatches==0) o[i]=-1;
}
}
}

void DoCalculations()
{
ShortDimensions();
ShortBoxes();
RemoveUnwantedBoxes();
}

void ShowResults()
{
int i; //Counter
int NumCounted=0; //Number of boxes counted
for (i=0; i<k; i++)
{
if (o[i]>=0)
NumCounted++;
}
printf("%d\n", NumCounted);
//WARNING: POSSIBLE PRESENTATION ERROR!!!
for (i=0; i<k-1; i++)
if (o[i]>=0)
printf("%d ", o[i]+1);
if (o[k-1]>=0)
printf("%d\n", o[k-1]+1);
//END OF WARNING
}

int main()
{
//Read the input and do calculations if there are input data
ReadInput();
while (ReadInputSuccess == 1)
{
DoCalculations();
ShowResults();
ReadInput();
}
//Exit
return 0;
}[/cpp]

I don't understand how you will choose the boxes to remove, in the second sample of the problemset:

Code: Select all

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 program shorts everything so we have:

Code: Select all

7)  01 02 03 04 05 06
1)  01 02 05 10 20 30
2)  03 07 09 11 15 23
5)  04 08 17 18 27 31
3)  04 14 24 34 40 50
4)  09 10 11 12 13 14
8)  09 18 21 37 47 80
6)  13 19 19 32 41 44

So we have "7 1 2 5 3 4 8 6" but the answer it suggests is "7 2 5 6" so 1,3,4,8 mus be removed right?

My program returns "7 2 5 4 6", and I think that "4" matches fine. Could you help me with the "Removing" Algorithm. THANK YOU.

[George]

I have the same problem. Please help me.
[cpp]#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

int k; //Number of boxes
int n; //Dimensionality
int d[30][10]; //Dimension length [box_number][dimension_number]
int o[30]; //Original order numbers
int ReadInputSuccess; //1 if reading data was successful, otherwise 0

void ReadInput()
{
if (scanf("%d %d", &k, &n) != 2)
{
ReadInputSuccess = 0;
return; //Exit if there are no input data
}
int i,j; //Counters
for (i=0; i<k; i++) //i=box number counter
for (j=0; j<n; j++) //j=dimensions counter
scanf("%d", &d[j]);
//Setup original order
for (i=0; i<k; i++)
o=i;
//Success
ReadInputSuccess=1;
}

void ShortDimensions()
{
//Short dimensions is boxes
int i,j,l; //Counters
//Vars used in shorting
int MinValue;
int PosForMinValue;
int t; //Temp for swapping
for (i=0; i<k; i++)
{
//Short numbers in d
for (j=0; j<n; j++)
{
MinValue=d[j];
PosForMinValue=j;
for (l=j; l<n; l++)
{
if (MinValue>d[l])
{
MinValue=d[l];
PosForMinValue=l;
}
}
//Swap d[PosForMinValue],d[j]
t=d[PosForMinValue];
d[PosForMinValue]=d[i][j];
d[i][j]=t;
}
}
}

int CompareBoxes(int Box1No, int Box2No)
{
//Compares all the dimensions of two boxes
//Parameters: the Numbers of 2 boxes in d[box_no]
//Returns 1 if the Box2 < Box1
//otherwise 0
int i;
//This will find a dimension that is not equal for both boxes
for (i=0; (i<n) && (d[Box1No][i]==d[Box2No][i]); i++);
//return the result by comparing a dimension that is not same
return ((d[Box1No][i]>d[Box2No][i])?1:0);
}

void SwapBoxes(int b1, int b2)
{
//Shap two boxes
//and setup original order
int t; //Temp for swapping
//swap original order first
t=o[b1];
o[b1]=o[b2];
o[b2]=t;
int i; //Counter
for (i=0; i<n; i++)
{
t=d[b1][i];
d[b1][i]=d[b2][i];
d[b2][i]=t;
}
}

void ShortBoxes()
{
//This will short all boxes
int i,j; //Counters
int MinBoxPos; //Position for the minimum box
for (i=0; i<k; i++)
{
//This will short the boxes
MinBoxPos=i;
for (j=i; j<k; j++)
{
if (CompareBoxes(MinBoxPos, j) == 1)
{
MinBoxPos=j;
}
}
//Swap
SwapBoxes(MinBoxPos, i);
}
}

int BoxNests(int b1, int b2)
{
//if b1 nests in b2, this function returns 1, otherwise 0
for (int i=0;i<n;i++)
{
//all the dimensions must be smaller to fit
if (d[b1][i]>=d[b2][i])
return 0;
}
return 1;
}

void RemoveUnwantedBoxes()
{
//This will remove boxes that doesn't nest (using the BoxNests function)
int i; //Counter
int NextBox, PrevBox;
//Check all the boxes (Except First and Last)
for (i=1;i<k-1;i++)
{
//Finds the Previous and Next box
//We need this to exclude boxes that are erased
for(NextBox=i+1;o[NextBox]==-1;NextBox++);
for(PrevBox=i-1;o[PrevBox]==-1;PrevBox--);

if (BoxNests(i,NextBox)==0 && BoxNests(PrevBox,i)==0)
o[i]=-1;
}
//Check the first and the last
//Find first the second box and the box before the last excluding the erased boxes
for(NextBox=1;o[NextBox]==-1;NextBox++);
for(PrevBox=k-2;o[PrevBox]==-1;PrevBox--);
//Now check
if (BoxNests(0,NextBox)==0)
o[0]=-1;
if (BoxNests(PrevBox,k-1)==0)
o[k-1]=-1;
}

void DoCalculations()
{
ShortDimensions();
ShortBoxes();
RemoveUnwantedBoxes();
}

void ShowResults()
{
int i; //Counter
int NumCounted=0; //Number of boxes counted
int LastBox; //The last box(used to output \n)
for (i=0; i<k; i++)
{
if (o[i]>=0)
NumCounted++;
}
printf("%d\n", NumCounted);
for(LastBox=k-1;o[LastBox]==-1;LastBox--);
for (i=0; i<k; i++)
if (o[i]>=0)
{
printf("%d", o[i]+1);
if (i==LastBox)
printf("\n");
else
printf(" ");
}
}

int main()
{
//Read the input and do calculations if there are input data
ReadInput();
while (ReadInputSuccess == 1)
{
DoCalculations();
ShowResults();
ReadInput();
}
//Exit
return 0;
}[/cpp]

[Ruslan Shevelyov]

George,

I wrote this simple autotester:
[cpp]
#include <cstdlib>
#include <fstream>
#include <iostream>
using namespace std;

void gen_test(){
int dim = rand()%3+1;
int num = rand()%5+1;
fstream testfile("in", ios_base::out);
testfile<<num<<' '<<dim<<'\n';
for(int i=0; i<num; i++){
for(int j=1; j<dim; j++)
testfile<<(rand()%1000)<<' ';
testfile<<(rand()%1000)<<'\n';
}
testfile.close();
}

void run_test(){
system("ac <in >out1");
system("wa <in >out2");
}
bool compare_results(){
fstream out1("out1");
fstream out2("out2");
int i, j;
out1>>i; out2>>j;
out1.close(); out2.close();
return (i==j);
}

int main(){
randomize();
for(int i=0; i<1e6; i++){
gen_test();
run_test();
cout<<'.';
if(!compare_results()){
cout << "\nmismatch!\n";
return 0;
}
}
}
[/cpp]

ac.exe is my (accepted) program, and wa.exe is your program.
These programs produce different output for this test:

5 2
806 507
372 316
138 30
380 523
345 530

4
3 2 4 1

5
3 2 5 4 1

As you can see, 5 is not less than 4.

[Ruslan Shevelyov]

danielrocha,

Your program gave strange output for this test (run for a minute or so):

6 5
622 413 899 408 333
471 304 534 644 914
11 529 348 268 542
581 374 527 557 669
888 397 159 70 722
373 303 788 71 255

1
1
1
1
1
1
1
1
2
55 100
1
1
2
4 1
1
1
2
501 128
1
1
1
1
2
279 277
1
1
2
516 388
1
1
1
1

Also my compiler reports:

wa2.cpp:
Warning W8066 wa2.cpp 34: Unreachable code in function encaixou(int,int)
Warning W8004 wa2.cpp 132: 'atual' is assigned a value that is never used in function main()

[Ruslan Shevelyov]

My old Pascal compiler said he don't know what "fillchar" is, and I already forgot the syntax... So I said #define fillchar(ARR, SIZE, VALUE) for ___idx:=1 to SIZE do ARR[___idx]:=VALUE; <evil grin> don't know if it is correct or not...
So he compiled the code, and for this test:

17 4
859 397 577 913
757 501 912 171
836 991 761 899
647 446 709 426
295 211 586 775
750 619 733 153
192 999 205 89
264 552 958 328
309 705 412 596
94 569 98 520
529 849 162 453
299 3 766 227
748 539 511 820
778 562 725 523
497 200 103 880
903 737 701 423
813 788 691 857

the answer was:

5
10 5 14 17 3
?GPC runtime error: Eoln is tested when Eof is on (#42)

I suppose correct answer is

6
10 9 4 13 17 3

[stx]

as many people before me I also have troubles with 103 problem
in brief algorithm look like
1. for each box sort its dimensions
2. sort boxes in lexicographic order
3. find the longest sequence using recursion

all examples (test input) from this forum work properly and give right output but i still have WA from online judge

if somebody has AC this problem can you send me you source to create randomise tester or can you check my code

i really doesn't understand what is happening
thanx
[cpp]
#include <stdio.h>
#include <string.h>

int cmp( int *a, int *b, int k)
{
/*
a < b => < 0
a = b => = 0
a > b => > 0
*/
int i = 0;
for( ; i < k && a[ i ] == b[ i ]; i++ );

if ( i == k )
return 0;
else if ( a > b )
return 1;
else
return -1;
}

int is_nested(int *a, int *b, int n )
{
/*
b nests a (a is nested in b) => 1
otherwise => 0
*/
int i;
for(i = 0; i < n; i++)
if ( a >= b )
return 0;

return 1;
}

int k = 0; /* number of boxes */
int n = 0; /* dimension */

int *boxes[30], /* box sequence */
start[30], /* flags if we need to start sequence from this box*/
sequence[30];

int res_seq[30], res_len = 0, seq_len = 0;

void build_seq( int start_at )
{
sequence[ seq_len++ ] = start_at;
int cur_len = seq_len;
for(int i = start_at + 1; i < k; i++ )
{

if ( is_nested( boxes[ start_at], boxes[ i ], n ) )
{
start[ i ] = 0;
seq_len = cur_len;

build_seq( i );

if ( res_len < seq_len )
{
res_len = seq_len;
memcpy(res_seq, sequence, seq_len * sizeof(int) );
}
}
}

}

int main()
{
int *box;
int e, i, j, s;

while ( scanf("%d %d", &k, &n) == 2 )
{
/* read and transform input sequence of boxes */
for( i = 0; i < k; i++ )
{
/* read each box sorting it dimensions in up order*/
box = new int[ n + 1 ];
for( j = 0; j < n; j++)
{
scanf("%d", &e);
for( s = 0; s < j && box[ s ] < e; s++ );
if ( s < j )
memmove(box + s + 1, box + s , sizeof( int ) * (j - s) );

box[ s ] = e;
}
box[ n ] = i;/* write input number of a box */

/* sort all boxes in seguence by lexicographic order*/
for( j = 0; j < i && cmp( boxes[ j ], box, k ) < 0; j++ );
for( s = i - 1; s >= j; s-- )
boxes[ s + 1 ] = boxes[ s ];

boxes[ j ] = box;

start[ i ] = 1;
}/* end of input */

/* proceed */
i = 0;
res_len = 0;
for( i = 0; i < k; i++)
{
if ( start[ i ] )
{
seq_len = 0;
build_seq( i );
}
}

/* output */
printf("%d\n", res_len);
for( i = 0; i < res_len; i++ )
printf("%d ", boxes[ res_seq[ i ] ][ n ] + 1 );
printf("\n");


/* free memory */
for( i = 0; i < k; i++ )
delete[] boxes[ i ];
}


return 0;
}

[/cpp]

[stx]

sorry to trouble everyone

everything is ok for now
i 've found bug in my code on 1 n input params

[freewish]

I got Runtime Error (SIGSEGV) in problem 103
Could any one tell me, what's wrong with it.
Thank you very much...

Here is my source code..


[c]#include <stdio.h>

int sub[31][31], box[31][11], maxsequence[31], maxlength;
int n, k;
void findout(int a[], int length, int position);

int main()
{
int s[31];
int ta, tb, tc, check, temp;

while(scanf("%d%d", &n, &k)==2)
{
for(ta=1; ta<=n; ta++)
{
for(tb=1; tb<=k; tb++)
scanf("%d",&box[ta][tb]);
for(tb=1; tb<=k ;tb++)
for(tc=tb+1; tc<=k; tc++)
if(box[ta][tb]>=box[ta][tc])
{
temp = box[ta][tb];
box[ta][tb]= box[ta][tc];
box[ta][tc]=temp;
}
}
for(ta=1; ta<=n; ta++)
for(tb=1; tb<=k; tb++)
sub[ta][tb]=0;
for(ta=1; ta<=n; ta++)
for(tb=ta+1; tb<=n; tb++)
{
for(check=0, tc=1; tc<=k ;tc++)
{
if(box[ta][tc]>box[tb][tc])
check++;
else if(box[ta][tc]<box[tb][tc])
check--;
}
if(check==k)
{
for(tc=1; tc<=n; tc++)
if(sub[ta][tc]==0)
{
sub[ta][tc]=tb;
break ;
}
}
else if(check==-k)
{
for(tc=1; tc<=n; tc++)
if(sub[tb][tc]==0)
{
sub[tb][tc]=ta;
break;
}
}
}

for(ta=1, maxlength=0; ta<=n; ta++)
{
s[1]=ta;
findout(s, ta, 1);
}

printf("%d\n",maxlength);
for(ta=maxlength; ta>=1; ta--)
printf("%d ", maxsequence[ta]);
printf("\n");
}

return 0;
}


void findout(int s[], int position, int length)
{
int ta, tb;
if(length>maxlength)
{
maxlength = length;
for(ta=1; ta<=length; ta++)
maxsequence[ta]=s[ta];

}
for(tb=1; sub[position][tb]!=0; tb++)
{
s[length+1]=sub[position][tb];
findout(s, sub[position][tb], length+1);
}
}[/c][/c]

[zlf_jack]

Could someone tell me what's the meaning of:
Warning: Your program would get a Presentation Error in a true contest.
The 24-hours judge interpretes it as an "Accepted" problem.
And my output is different from the sample output!
what's the meaning of :
If there is more than one longest nesting string then any one of them can be output.

Here is my c++ source code:

-----------------------------------------------------------------------------------

#include<iostream.h>

const int maxB=30;//max boxes number;
const int maxD=10;//max boxes dimention；

int data[maxB][maxD]={0};//store all boxes information;
//int Ration[maxB][maxB]={0};//each boxes relation:Ration[j]=1,means that i can load j;
int dIndex[maxB]={0}; //sorted information;
int DP[maxB][2]={0};//DP[A][0]:the longest nested chain legnth which end at A;
//DP[A][1]:the nearest boxes which can pack A of the longest length;
int BNum;//boxes bumber;
int DNum;//dimention number;
int maxL;//the longest length;
int maxLP;//the innerest boxes index;

//let all boxes'dimention sorted as descending;
void sortD(void)
{
int i,j,k,temp;
for(i=0; i<BNum ;i++)
{
for(j=0;j<DNum;j++)
{
for(k=j+1;k<DNum ;k++)
{
if(data[k]>data[j])
{
temp=data[k];
data[k]=data[j];
data[j]=temp;
}
}
}
}
}

//let all boxes sorted as descending,information stored in dIndex;

bool IsBig(int a,int b)
{
int i=0;
while(i<DNum)
{
if(data[a]>data)
return true;
if(data[a]<data[i])
return false;
i++;
}
return true;
}

void sortB(void)
{
int i,j,temp;
for(i=0;i<BNum;i++)
dIndex[i]=i;
for( i=1;i<BNum;i++)
{
for(j=0;j<i;j++)
{
if( IsBig(dIndex[i],dIndex[j]) )
{
temp=dIndex[i];
dIndex[i]=dIndex[j];
dIndex[j]=temp;
}
}
}
}

bool IsPackable(int a,int b) //if a can be packed into b,return true;
{
int i=0;
while(i<DNum)
{
if(data[a][i]>=data[i])
return false;
i++;
}
return true;
}


void getMaxL(void)
{
int i,j,tempmax;
//init DP;
for(i=0;i<BNum;i++)
{
DP[i][0]=0;
DP[i][1]=-1;
}
maxL=1;
maxLP=0;
DP[0][0]=1;
DP[0][1]=-1;
for(i=1;i<BNum;i++)
{
for(j=0;j<i;j++)
{
tempmax=DP[j][0]+1;
if(tempmax>DP[i][0] && IsPackable(dIndex[i],dIndex[j]))
{
DP[i][0]=tempmax;
DP[i][1]=j;
if(tempmax>maxL)
{
maxL=tempmax;
maxLP=i;
}
}
}
}
}

bool Input(void)
{
int i,j;
while( cin>>BNum>>DNum )
{
for(i=0;i<BNum;i++)
for(j=0;j<DNum;j++)
cin>>data[i][j];
return true;
}
return false;
}

void print(void)
{
cout<<maxL<<endl;
while(DP[maxLP][1]>-1)
{
cout<<(dIndex[maxLP]+1)<<' ';
maxLP=DP[maxLP][1];
}
cout<<(dIndex[maxLP]+1)<<' '<<endl;
}

void main(void)
{
while(Input())
{
sortD();
sortB();
getMaxL();
print();
}
}[cpp][/cpp]

[Maarten]

your program prints "3 1 2 4 5 \n" but it should be "3 1 2 4 5\n" (that is, no space at the end of line).

P.S. Please use formattting tags to post your code!

[zlf_jack]

thanks! i didn't know how to use formatting tag!
And how about help me with problem 101?[/cpp]

[Maarten]

101 is a nasty problem.. you have to be very precise in your coding but basically it is just simulation