Page 7 of 14
Where to find good test data file???
Posted: Sat Jan 22, 2005 7:36 pm
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.
Posted: Sun Jan 23, 2005 7:17 am
by ImLazy
This input:
1 1
1
1 2
1 1
the output should be:
1
1
1
1
Requesting: IOdata # 103
Posted: Sun Jan 23, 2005 1:24 pm
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
Posted: Sun Jan 23, 2005 1:30 pm
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.
Posted: Mon Jan 24, 2005 2:35 pm
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.
103 - Compiler Error
Posted: Thu Mar 17, 2005 5:35 am
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;
}
Posted: Thu Mar 17, 2005 5:52 am
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.
Posted: Thu Mar 17, 2005 7:45 am
by Tarsoav
Been thankful.
103 WA????!!!!
Posted: Fri Apr 01, 2005 9:45 am
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;
}
103 : runtime error (sigsegv)
Posted: Thu Apr 07, 2005 11:39 am
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;
}
Posted: Thu Apr 07, 2005 12:06 pm
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,
Posted: Thu Apr 07, 2005 3:19 pm
by 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...
Posted: Thu Apr 07, 2005 4:32 pm
by ugrash
Yes, for the ecological bin problem, it would have been too long
i will try to enter static size for my arrays
Posted: Thu Apr 07, 2005 5:00 pm
by ugrash
I tried to replace
order, solution, solutemp, boxes and buffer by fixed-size arrays, but i still have "Invalid memory reference"
Posted: Thu Apr 07, 2005 5:26 pm
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]);