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

Post Reply
ElSoloMar
New poster
Posts: 9
Joined: Thu Jan 09, 2003 9:42 am
Contact:

Where to find good test data file???

Post by 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.
Last edited by ElSoloMar on Sun Jan 23, 2005 1:47 pm, edited 1 time in total.
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy »

This input:
1 1
1
1 2
1 1
the output should be:
1
1
1
1
I stay home. Don't call me out.
ElSoloMar
New poster
Posts: 9
Joined: Thu Jan 09, 2003 9:42 am
Contact:

Requesting: IOdata # 103

Post by 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
New poster
Posts: 9
Joined: Thu Jan 09, 2003 9:42 am
Contact:

Post by 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
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by 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.
I stay home. Don't call me out.
Tarsoav
New poster
Posts: 3
Joined: Thu Mar 17, 2005 5:26 am
Location: Brazil

103 - Compiler Error

Post by 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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by 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
New poster
Posts: 3
Joined: Thu Mar 17, 2005 5:26 am
Location: Brazil

Post by Tarsoav »

Been thankful.
gladiatorcn
New poster
Posts: 8
Joined: Wed Mar 30, 2005 9:46 am

103 WA????!!!!

Post by 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
New poster
Posts: 5
Joined: Fri Apr 01, 2005 2:06 pm

103 : runtime error (sigsegv)

Post by 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
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by 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,
Understanding a problem in a natural way will lead to a natural solution
jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by jakabjr »

I'm sorry, I confused the prob with ecological bins(102) :o . 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... :cry:
ugrash
New poster
Posts: 5
Joined: Fri Apr 01, 2005 2:06 pm

Post by ugrash »

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

i will try to enter static size for my arrays
ugrash
New poster
Posts: 5
Joined: Fri Apr 01, 2005 2:06 pm

Post by ugrash »

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

:cry:
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by 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]);
Post Reply

Return to “Volume 1 (100-199)”