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

Carthage
New poster
Posts: 12
Joined: Wed Oct 29, 2003 8:05 pm
Yes, 101 is a real problem, probably because I misunderstood the instructions. My first algorithm gives the correct sample output, but with the inputs here, it went haywire! Anyway, it took me about a dozen WAs before I finally knew that the algorithm was wrong.

Anyway, 118 is an easier problem.
My ideas on solving programming problems are 91% common sense, practicality and luck, 8% pure knowledge, and 1% extreme Math.

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:
dawynn wrote: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.
David, I was thinking about this part... Consider this boxes (with sorted dimensions):
(3, 3, 6, 6, 6, 6)
(2, 3, 5, 5, 5, 5)
(1, 3, 5, 5, 5, 5)
(0, 3, 9, 9, 9, 9)

It's easy to see that none of them will fit in each other (look 2nd dimension). If they don't come in this order, they will sorted, what is pointless in this case. Later, during DP, they will be checked again, what is pointless too.

Maybe it is a good idea to sort them into groulps instead of sorting them with qsort, for example. Maybe any box of groulp N would fit in any box of groulp N+1, while inside groulp N, there could be or not boxes that fit in each other...

The idea is not clear for me, but I would like to know the optimum method. There are lots of people with 0 millisec in this prob.

What do you think?

seg10
New poster
Posts: 4
Joined: Thu May 29, 2003 7:49 am

### 103: wrong answer? *frustrated*

the amount of time I spent on this problem is enormous and embarassing. I have what I believe is a DP solution to the problem. Yet, it's still marked as wrong. I would be indebted to anyone who can point me in the proper direction!

[c]
#include <stdlib.h>
#include <stdio.h>

struct node {
int id;
int dim[10];
int length;
struct node *next;
};

struct node *initB();
int comparable(struct node *a, struct node *b);
int compD(const void *a, const void *b);
int compB(const void *a, const void *b);

int main(){
int maxD;
int maxB;
struct node *boxes[30];

int x, y;
struct node *t;
int maxBox;
int maxLength;

while(scanf("%d %d", &maxB, &maxD) != -1){

/* input */
for(x = 0; x < maxB; x++){
boxes[x] = initB();
boxes[x]->id = x+1;
for(y = 0; y < maxD; y++)
scanf("%d", &boxes[x]->dim[y]);
qsort(&boxes[x]->dim[0], maxD, sizeof(int), compD);
}
qsort(&boxes[0], maxB, sizeof(struct node *), compB);

/* Determination of maximum in the poset */
maxLength = 0;
for(x = maxB-2; x > -1; x--){
for(y = x+1; y < maxB; y++)
if(comparable(boxes[x], boxes[y]) &&
boxes[y]->length > boxes[x]->length-1){
boxes[x]->length = boxes[y]->length+1;
boxes[x]->next = boxes[y];
}
if(boxes[x]->length > maxLength){
maxLength = boxes[x]->length;
maxBox = x;
}
}

/* Print out */
for(t = boxes[maxBox]; t != NULL; t = t->next)
printf("%d ", t->id);
printf("\n");
}
}

struct node *initB(){
struct node *restless;
int x;
restless = (struct node *)malloc(sizeof(struct node));
for(x = 0; x < 30; x++)
restless->dim[x] = -1;
restless->length = 1;
restless->next = NULL;
restless->id = -1;
return restless;
}
int comparable(struct node *a, struct node *b){
int type;
int x;
if(a->dim[0] == b->dim[0])
return 0;
else
if(a->dim[0] > b->dim[0])
type = 1;
else
type = -1;

for(x = 0; x < 30 && a->dim[x] != -1; x++)
if(a->dim[x] == b->dim[x]){
return 0;
}else
if(type == -1 && a->dim[x] > b->dim[x])
return 0;
else if(type == 1 && a->dim[x] < b->dim[x])
return 0;
if(b->next == NULL)
return 1;
else
return(comparable(a, b->next));
}

int compD(const void *a, const void *b){
int c = *(int *)a;
int d = *(int *)b;
int x;

if(c > d)
return 1;
else if(d > c)
return -1;
else return 0;
}
int compB(const void *a, const void *b){
struct node c = **(struct node **)a;
struct node d = **(struct node **)b;
int x;

for(x = 0; x < 30 && c.dim[x] != -1; x++)
if(c.dim[x] > d.dim[x])
return 1;
else if(c.dim[x] < d.dim[x])
return -1;

return 0;
}

[/c]

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

### Re: 103: wrong answer? *frustrated*

seg10 wrote:I have what I believe is a DP solution to the problem.
In this problem I've made a graph (edge A->B if A nests in B) and then used graph search in topological order (I think it's a bit DP solution).

emotion
New poster
Posts: 1
Joined: Sun Dec 28, 2003 2:31 pm
Location: Moscow, Russia
Contact:
can you help?
i try out all my test cases but still get WA.
can you generate more TC?
[cpp]//Problem: 103
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include <iostream>

#define MAX 1000000000
using namespace std;

#ifndef ONLINE_JUDGE
#define cs ccin
#include <fstream>
ifstream ccin("input.txt");
#else
#define cs cin
#endif

string itos(int i) {
string res;
stringstream s;
s << i;
s >> res;
return res;
}

string toUP(string s) {
for (unsigned int i = 0; i < s.size(); i++) {
if (s >= 'a' && s <= 'z') {
s -= 32;
}
}
return s;
}

struct bx {
vector <int> dim;
int num;

static bool cmpByWeight(bx a, bx b) {
int l = a.dim.size();
for (int i = 0; i < l; i++) {
if (a.dim < b.dim) {
return true;
}
if (a.dim > b.dim) {
return false;
}
}
return false;
}

static bool isFit(bx a, bx b) {
int l = a.dim.size();
for (int i = 0; i < l; i++) {
if (a.dim >= b.dim) {
return false;
}
}
return true;
}
};

int main(int argc, char* argv[]) {
while (!cs.eof()) {
int k = 0 , n = 0;
vector <bx> boxes;
cs >> k >> n;
if (cs.eof()) {
break;
}

if (k <= 0 || n <= 0) {
continue;
}

for (int i = 0; i < k; i++) {
bx b;
b.num = i + 1;
for (int x = 0; x < n; x++) {
int size = 0;
cs >> size;
b.dim.push_back(size);
}
sort(b.dim.begin(), b.dim.end());
boxes.push_back(b);
}

stable_sort(boxes.begin(), boxes.end(), bx::cmpByWeight);

vector <pair<int, string> >data(boxes.size());
for (int i = 0; i < boxes.size(); i++) {
data.first = 1;
data[i].second = itos(boxes[i].num);
}

int maxN = 1;
int maxI = 0;
for (int i = boxes.size() - 2; i >= 0; i--) {
for (int j = boxes.size() - 1; j > i; j--) {
if (bx::isFit(boxes[i], boxes[j]) && data[i].first <= data[j].first + 1) {
data[i].first = data[j].first + 1;
data[i].second = itos(boxes[i].num);
data[i].second += " ";
data[i].second += data[j].second;
if (maxN <= data[i].first) {
maxN = data[i].first;
maxI = i;
}
}
}
}

cout << maxN << "\n" << data[maxI].second << "\n";
};

#ifndef ONLINE_JUDGE
cout << "\npress a key\n";
getchar();
#endif
return 0;
}
[/cpp]

Ruslan Shevelyov
New poster
Posts: 15
Joined: Fri Aug 08, 2003 8:13 pm
Location: Russia, Moscow
Contact:
Сгенерил полмиллиона тестов, ошибок не нашёл...
www.Find-a-Drug.org distributed computing project

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
This is a public forum and it's not polite to use Russian, esp. since you know English well.

Ruslan Shevelyov
New poster
Posts: 15
Joined: Fri Aug 08, 2003 8:13 pm
Location: Russia, Moscow
Contact:
Babelfish's English is much better than mine.

scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am
Your program sorted the input to:
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
4 does not belong in the sequence because 17 is not less than 11 and others on that row are also not less than row 5

scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am
Here is an input that catches some errors in logic.
input
8 3
1 10 1
8 8 8
4 6 6
7 5 7
5 2 1
1 2 1
6 2 4
5 5 3
output
5
6 8 3 4 2

kiburm
New poster
Posts: 2
Joined: Sat Jan 24, 2004 7:30 am

### #103 WA but all test seems gets right answer

[cpp]
#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
using namespace std;

class Run
{
int abox[30][10];
int aboxindex[30];
int alengthtable[30];
int apath[30][10];
int imaxlengthindex;
int i_box,i_dim;
public:

vector<string> Split(const string& source,const string& delim )
{
size_t s,e=0;
vector<string> r;
for(;;)
{ s=source.find_first_not_of(delim,e);
e=source.find_first_of(delim,s);
if(s==source.npos) break;
r.push_back(source.substr(s,e-s));
}
return r;
}
public:
string Get_input()
{
char buf[255];
cin.getline(buf,255,'\n');
return string(buf);
}

void Init()
{
for(int i=0;i<30;i++)
{
for(int j=0;j<10;j++)
{
abox[j]=0;
apath[j]=0;
}
aboxindex=0;
alengthtable=0;
}
}

int Get_boxes()
{
vector<string> info= Split(Get_input()," ");
if(info.size()!=0) //input이 없으면 끝내야쥐
{
i_box=atoi(info[0].c_str());
i_dim=atoi(info[1].c_str());
if(i_dim >10 ||i_dim<1 || i_box>30 || i_box<0) return 2;
for(int i=0;i<i_box;i++)
{
vector<string> boxvertex= Split(Get_input()," ");
for(int j=0;j<i_dim;j++)
{
abox[j]=atoi(boxvertex[j].c_str()); //BOX 점들 입력
}
aboxindex=i;
}
return 1;
}
else
return 0;
}

void Get_sorted_list() //box들을 각각 오름차순 정렬
{
for(int i=0;i<i_box;i++)
{
for(int j=1;j<i_dim;j++)
{
int k=j;
int temp=abox[j];
while(abox[k-1]>temp && k>0)
{
abox[k]=abox[k-1];
k--;
}
abox[i][k]=temp;
}
}
}

void Get_sorted_Box_list() //첫번째 dimension 으로 정렬.
{
for(int i=1;i<i_box;i++)
{
int k=i;
int t=aboxindex[i];
int temp=abox[aboxindex[k]][0];
while(abox[aboxindex[k-1]][0]>temp && k>0)
{
aboxindex[k]=aboxindex[k-1];
k--;
}
aboxindex[k]=t;
}
}

bool check_nest(int s, int c)
{
for(int i=0;i<i_dim;i++)
{
if( abox[aboxindex[s]][i] <= abox[aboxindex[c]][i] )
return false;
}
return true;
}

void Get_max_length()
{
for(int i=0;i<i_box;i++)
{
alengthtable[i]=1;
apath[i][0]=aboxindex[i];
}
for(int i=1;i<i_box;i++)
{
for(int j=i-1;j>=0;j--)
{
if(check_nest(i,j))
{
int temp=alengthtable[j]+1;
if(temp>alengthtable[i])
{
alengthtable[i]=temp;
for(int k=0;k<temp-1;k++)
apath[i][k]=apath[j][k];
apath[i][temp-1]=aboxindex[i];
}
}
}
}
int imaxlength=0;
for(int i=0;i<i_box;i++)
{
if(alengthtable[i]>imaxlength)
imaxlengthindex=i;
}
}

void Printout()
{
if(i_box>0)
{
int result=alengthtable[imaxlengthindex];
cout<<result<<endl;
for(int i=0;i<result-1;i++)
{
cout<<apath[imaxlengthindex][i]+1<<" ";
}
cout<<apath[imaxlengthindex][result-1]+1<<endl;
}
}

void Process()
{
int t;
while((t=Get_boxes())>=1)
{
if(t==1)
{
Get_sorted_list();
Get_sorted_Box_list();
Get_max_length();
Printout();
}
Init();
}
}

};
int main(int argc, char *argv[])
{
Run run;
run.Process();
return 0;
}
[/cpp]

i used DP which someone posted.
sort by dimesion. and sort by first dimension.
and check nest bottom up.
could anyone test result with accepted one?
thnaks before....

scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am
http://people.eecs.ku.edu/~rucker/valladolid/p103.exe

Here is my AC solution. This executable will create a input file and create a solution output file. Just run the input file through your program and double check it against the output file. If you get the same output as the output file then run the program again to create a new input file and output file.

kiburm
New poster
Posts: 2
Joined: Sat Jan 24, 2004 7:30 am

### oops... the algorithm was absouletely right..

but i mistaked at assigning array range....

all i tested was that legth was less than 10.....
who gets stuck in this problem should try input length greater.

aditya
New poster
Posts: 5
Joined: Mon Jan 12, 2004 12:44 pm

### Compiler Error

Helllo Everyone,

My program runs fine on my computer.
i am using gcc with -Wall and -pedantic.......but when i submit the problem via Submit-o-matic i get a compiler error............this is driving me crazy......everything seems to be right.....
please help..................

scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am
well sure.... some code would be nice :)