103 - Stacking Boxes

[Carthage]

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.

[Algoritmo]

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]

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]

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]

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]

Сгенерил полмиллиона тестов, ошибок не нашёл...

[Krzysztof Duleba]

This is a public forum and it's not polite to use Russian, esp. since you know English well.

[Ruslan Shevelyov]

Babelfish's English is much better than mine.

[scruff]

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]

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]

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

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]

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]

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]

well sure.... some code would be nice :)