103 - Stacking Boxes

[ElSoloMar]

Guys,

Is there some way to put our hand on good test data files to test our
programs? The problems provide some example but they are generally a few and
they generally do not test for extreme, particular, or special
cases. I propose the following: every time we start solving a problem
we can request what we could call I/O data (IOdata) for the problem that we are
working on. People in the forum should provide their IOdata files of special,
extreme, and particular cases... also, the answers! Good IOdata without
answers worth nothing! When you request an IOfile make sure that the topic
includes the keyword "IOdata" followed by the problem number, keeping this
simple convention will make it easy to find all a good set of data to test your
solutions. i.e.:

Code: Select all

   Requesting IOdata 103
   Requesting: IOdata # 103
   Requesting IOdata for Problem 103

personally, I like the second one! I am sure that in a short period of
time we will have the IOdata for all the problems. Remember,

Code: Select all

 IODATA WITHOUT ANSWERS WORTH NOTHING AND YOU ARE EVIL! 

I am working on problem 103 ... let me go ahead and request the IOdata for this problem.

[ImLazy]

This input:
1 1
1
1 2
1 1
the output should be:
1
1
1
1

[ElSoloMar]

Hey,

If you do not know what this topic is all about, then read the topic "Where to find good test data file???" posted shortly before this one; or just go there directly http://online-judge.uva.es/board/viewtopic.php?t=7350

[ElSoloMar]

Dear ImLazy and everybody,

Thank you for your replay! that one look like a good particular case. Would you happen to have some cases close to the memory limits impose by the problem? 30 boxes with dimensionality 10 (a 30x10) . Or cases that test the range of the input types in the function signatures, meaning, when the value of the dimensions is really large and should be handled with the proper storage types:

int : 16-bits ---> the largest value for a box dimention can be 32'767
unsigned: 16-bits ---> the largest value for a box dimention can be 65'535
unsigned long: 32-bits ---> the largest value for a box dimention can be 4'294'967'295

By the way, do not post your IOdata here! Post them under the topic "Requesting: IOdata # 103" located at http://online-judge.uva.es/board/viewtopic.php?t=7354 ; in that way every body should be able to find them through the topic.

[ImLazy]

Sorry, I got AC in this problem at my first try, so I didn't try any complex input. What I can tell you is I use all data of int type in my code.

[Tarsoav]

I compel with g++ 2.95.3, g++ 3.3.3 and VC6. But when I submit gives Compiler Error. Somebody can help me?

Code: Select all

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ostream.h>
using namespace std;

int compint( const void *pa, const void *pb)
{
	int *a = (int*)pa;
	int *b = (int*)pb;
	if( (*a) < (*b) )
		return -1;
	if( (*a) > (*b) )
		return 1;
	return 0;
}

class CCaixa : public vector<int>
{
public:
	int iOrdemInsert;
	void sort();
};

void CCaixa::sort()
{
	int i;
	int* pData = new int[size()];
	for(i=size()-1;i>=0;i--)
		pData[i] = (*this)[i];
	qsort(pData, size(), sizeof(int), compint);
	for(i=size()-1;i>=0;i--)
		(*this)[i] = pData[i];
	delete[] pData;
}

int conpCCaixa( const void *pa, const void *pb)
{
	CCaixa* a = (CCaixa*)pa;
	CCaixa* b = (CCaixa*)pb;
	
	for(int i=a->size()-1;i>=0;i--)
	{
		if( (*a)[i] < (*b)[i] )
			return -1;
		if( (*a)[i] > (*b)[i] )
			return 1;
	}
	return 0;
}

class CListaCaixas : public vector<CCaixa>
{
public:
	void sort();
};

void CListaCaixas ::sort()
{
	int i;
	CCaixa* pData = new CCaixa[size()];
	for(i=size()-1;i>=0;i--)
		pData[i] = (*this)[i];
	qsort(pData, size(), sizeof(CCaixa), conpCCaixa);
	for(i=size()-1;i>=0;i--)
		(*this)[i] = pData[i];
	delete[] pData;
}

// Globais
CListaCaixas caixas;
int l, d, i, j, aux;
vector<int> resp, temp;

void calcula(int i)
{
	if(i>=l)
	{
		return;
	}
	
	bool bOk = true; 
	if(temp.size()>0)
	{
		for(aux=0;aux<d;aux++)
		{
			if(caixas[temp.back()][aux]>=caixas[i][aux])
				break;
		}
		
		bOk = (aux==d);
	}
	
	if(bOk)
	{
		temp.push_back(i);
	}
	
	for(int j=i+1;j<l;j++)
	{
		calcula(j);
	}
	
	if(resp.size()<temp.size())
	{
		resp = temp;
	}
	
	if(bOk)
	{
		temp.pop_back();
	}
}

int main()
{
	while(scanf("%d %d", &l, &d)!=EOF)
	{
		caixas.resize(l);
		for(i=0;i<l;i++)
		{
			caixas[i].clear();
			for(j=0;j<d;j++)
			{
				scanf("%d", &aux);
				caixas[i].push_back(aux);
			}
			caixas[i].iOrdemInsert = i;
			caixas[i].sort();
		}
		caixas.sort();

		resp.clear();
		temp.clear();
		for(i=0;(i<l)&&(resp.size()<(l-i-1));i++)
		{
			calcula(i);
		}
		
		printf("%d\n", resp.size());
		printf("%d", caixas[resp[0]].iOrdemInsert+1);
		for(i=1;i<resp.size();i++)
		{
			printf(" %d", caixas[resp[i]].iOrdemInsert+1);
		}
		printf("\n");
	}
	
	return 0;
}

[Krzysztof Duleba]

If you submit via the OJ www interface, you'll have the exact error message delivered to your email. Anyway, try to remove <ostream.h> as you seem not to use it at all, maybe that will help.

[Tarsoav]

Been thankful.

[gladiatorcn]

My program s produced the correct answers to all the sample inputs, but got a wa. Plz help!!!!!!!!!!
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int k,n;
int box[30][12];

int cmp1(const void *p,const void *q){
const int *a=p,*b=q;
int i,s1,s2;

for(i=0,s1=1,s2=1;i<n;i++)
{
s1*=*(a+i);
s2*=*(b+i);
}
return s1>s2?1:(s1==s2?0:-1);
}

int cmp2(const void *p,const void *q){
const int *m=p,*n=q;
return *m>*n?1:(*m==*n?0:-1);
}

int fitin(int a,int b)
{
int i;

for(i=0;i<n;i++)
if(box[a][i]>=box[b][i])
return 0;
return 1;
}

int main()
{
int i,j,p,q,length,maxlength;
int s[30],f[30];

for(i=0;i<30;i++)
{
for(j=0;j<10;j++)
box[i][j]=1;
box[i][11]=1;
}
while(scanf("%d%d",&k,&n)==2)
{
maxlength=0;
for(i=0;i<k;i++)
{
box[i][10]=i+1;
for(j=0;j<n;j++)
scanf("%d",&box[i][j]);
}
qsort(box,k,12*sizeof(int),cmp1);
for(i=0;i<k;i++)
qsort(box[i],n,sizeof(int),cmp2);
for(i=0;i<k;i++)
{
if(box[i][11]==-1) continue;
q=0;
j=i;p=i+1;
s[q++]=box[j][10];
box[j][11]=-1;
length=1;
while(j<k&&p<k)
{
if(fitin(j,p)==1)
{
length++;
s[q++]=box[p][10];
box[p][11]=-1;
j=p;
p++;
}
else p++;
}
if(length>maxlength)
{
maxlength=length;
memcpy(f,s,k*sizeof(int));
}
}
printf("%d\n",maxlength);
for(i=0;i<maxlength-1;i++)
printf("%d ",f[i]);
printf("%d\n",f[maxlength-1]);
}
return 0;
}

[ugrash]

Hi,

my code runs perfectly on my computer, but when I submit it, i have a Segmentation Fault....

Can somebody help ???


#include <stdio.h>

long boxdiff(long *boxa, long *boxb, long dim)
{
long diff = 0, i = 0;
while(diff == 0 && i < dim)
{
diff = boxa - boxb;
i++;
}
return diff;
}

void triboxs(long **boxs, long dim, long nbr, long *order)
{
long o,p,t;
long *temp;
for(o=nbr-1;o>=0;o--) for(p=0;p<o;p++) if(boxdiff(boxs[p],boxs[p+1],dim)>0)
{
temp=boxs[p];
boxs[p]=boxs[p+1];
boxs[p+1]=temp;
t=order[p];
order[p]=order[p+1];
order[p+1]=t;
}
}

void tribox(long *box, long dim)
{
long o,p,temp;
for(o=dim-1;o>=0;o--) for(p=0;p<o;p++) if(box[p]>box[p+1])
{
temp=box[p];
box[p]=box[p+1];
box[p+1]=temp;
}
}

long fitin(long *boxa, long *boxb, long dim)
{
long i, resultat = 1;
for(i=0;i<dim;i++) if(boxa>boxb) resultat--;
return resultat;
}

int main(long argc, char *argv[])
{
long i, j, k, l, nbrboxes, nbrdims, maxresult, exmaxresult;
long **boxes;
char *buffer;
long *ordre;
long *solution;
long *solutemp;
buffer=(char*)malloc(3000*sizeof(char));
while(scanf("%d %d", &nbrboxes, &nbrdims)==2)
{
maxresult = 1;
exmaxresult = 0;
fflush(stdin);
ordre=(long*)malloc(nbrboxes*sizeof(long));
solution=(long*)malloc(nbrboxes*sizeof(long));
solutemp=(long*)malloc(nbrboxes*sizeof(long));
boxes=(long**)malloc(nbrboxes*sizeof(long*));
for(i=0;i<nbrboxes;i++)
{
ordre=i;
solution=-1;
solutemp=-1;
boxes=(long*)malloc(nbrdims*sizeof(long));
gets(buffer);
boxes[0] = atoi(strtok(buffer," "));
for(j=1;j<nbrdims;j++) boxes[j] = atoi(strtok(NULL, " "));
tribox(boxes[i],nbrdims);
}
if (nbrboxes == 1)
{
printf("1\n1\n");
}
else
{
triboxs(boxes,nbrdims,nbrboxes,ordre);
exmaxresult=0;
for(k=1;k<nbrboxes;k++)
{
maxresult=1;
solutemp[0]=k-1;
j=0;
for(i=k;i<nbrboxes;i++)
{
if(fitin(boxes[solutemp[j]],boxes[i],nbrdims) == 1)
{
j++;
solutemp[j]=i;
maxresult++;
}
}
if(maxresult>exmaxresult)
{
memcpy(solution,solutemp,nbrboxes*sizeof(long));
exmaxresult=maxresult;
}
for(l=0;l<nbrboxes;l++) solutemp[l]=-1;
}
k=0;
printf("%d\n",exmaxresult);
while(solution[k]!=-1 && k < nbrboxes)
{
printf("%d ",ordre[solution[k]]+1);
k++;
}
printf("\n");
}
}
return 0;
}

[jakabjr]

The first and obvious problem with this code is that it's WAY too long, thus complicated, thus bug prone. I did not read it, my guess is an array limit exceeded because of a "special" test case. However, there is a better way: look around for previous topics on 103 and look at those algorithms. I remember seeing one that must have been about 25 lines long, and EASY!

Best regards,

[jakabjr]

I'm sorry, I confused the prob with ecological bins(102) . My first observation stands though, plus you should consider not using malloc, especially for n, which is given (1 to 10), and for k 100 should suffice.
I get WA on this one though the test cases I've seen on forum work with my code. I've combined them:

Code: Select all

5 2
3 7
8 10
5 2
9 11
21 18
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
5 1
3
5
5
2
1
1 4
4 5 6 4
5 3
1 2 3
2 3 4
3 4 5
4 5 6
6 7 8
3 3
1 1 1
1 2 2
1 3 3

My output is

Code: Select all

5
3 1 2 4 5
4
7 2 5 8
4
5 4 1 2
1
1
5
1 2 3 4 5
1
1

If anyone has any suggestions...

[ugrash]

Yes, for the ecological bin problem, it would have been too long

i will try to enter static size for my arrays

[ugrash]

I tried to replace
order, solution, solutemp, boxes and buffer by fixed-size arrays, but i still have "Invalid memory reference"

[mf]

Your program crashed on my system when given sample input at the line:

Code: Select all

for(j=1;j<nbrdims;j++) boxes[i][j] = atoi(strtok(NULL, " ")); 

(I suppose that strtok() somehow returned NULL, and that crashed atoi().)

You can read integers by simply calling scanf("%d", ...). E.g. instead of all those gets(), strtok(), atoi() you could write:

Code: Select all

for (j = 0; j < nbrdims; j++)
        scanf("%d", &boxes[i][j]);