103 - Stacking Boxes

[Krzysztof Duleba]

"not" is a restricted name.

[alltoucher]

"not" is a restricted name.

You are right!!!! Thanks!!!

[prodigyt]

I'd like you to test my input for the Stacking Boxes problem (#103), give an output and also answer how long does your program take to generate it.

Code: Select all

30 10
30 31 32 33 34 35 36 37 38 39
29 30 31 32 33 34 35 36 37 38
28 29 30 31 32 33 34 35 36 37
27 28 29 30 31 32 33 34 35 36
26 27 28 29 30 31 32 33 34 35
25 26 27 28 29 30 31 32 33 34
24 25 26 27 28 29 30 31 32 33
23 24 25 26 27 28 29 30 31 32
22 23 24 25 26 27 28 29 30 31
21 22 23 24 25 26 27 28 29 30
20 21 22 23 24 25 26 27 28 29
19 20 21 22 23 24 25 26 27 28
18 19 20 21 22 23 24 25 26 27
17 18 19 20 21 22 23 24 25 26
16 17 18 19 20 21 22 23 24 25
15 16 17 18 19 20 21 22 23 24
14 15 16 17 18 19 20 21 22 23
13 14 15 16 17 18 19 20 21 22
12 13 14 15 16 17 18 19 20 21
11 12 13 14 15 16 17 18 19 20
10 11 12 13 14 15 16 17 18 19
9 10 11 12 13 14 15 16 17 18
8 9 10 11 12 13 14 15 16 17
7 8 9 10 11 12 13 14 15 16
6 7 8 9 10 11 12 13 14 15
5 6 7 8 9 10 11 12 13 14
4 5 6 7 8 9 10 11 12 13
3 4 5 6 7 8 9 10 11 12
2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10

Thx in advance.

[chunyi81]

My AC code produces the following output in around 20ms on a 1.2GHz Unix Server. The slow time is due to the usage of cin/cout.

Code: Select all

30
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

[prodigyt]

Great. Now I'm at home in this problem. Thank you!

[guitarlover]

Currently, my program got WA.
For this input, my output is correct:
Input:
5 2
41 595
291 836
350 602
483 548
537 624

My Output:
3
1 3 5

However, with an accepted code which I found in this forum, the output is wrong
Output:
2
1 2

Here is the AC code(which produce wrong output for this input)
1. You can try submit this code, just to clarify that it is accepted.
2. Run the program to see the output.
3. Conclude that something is wrong with OJ. Otherwise, please clarify why.

P/S: Dun claim AC code posting to me. I just copy it from here
http://online-judge.uva.es/board/viewto ... =103+input

Tks

// Code compiled with VS 7

#include <iostream>
using namespace std;

#define OJ
const int maxB=30;//max boxes number;
const int maxD=10;//max boxes dimention；

int data[maxB][maxD]={0};//store all boxes information;
//int Ration[maxB][maxB]={0};//each boxes relation:Ration[j]=1,means that i can load j;
int dIndex[maxB]={0}; //sorted information;
int DP[maxB][2]={0};//DP[A][0]:the longest nested chain legnth which end at A;
//DP[A][1]:the nearest boxes which can pack A of the longest length;
int BNum;//boxes bumber;
int DNum;//dimention number;
int maxL;//the longest length;
int maxLP;//the innerest boxes index;

//let all boxes'dimention sorted as descending;
void sortD(void)
{
int i,j,k,temp;
for(i=0; i<BNum ;i++)
{
for(j=0;j<DNum;j++)
{
for(k=j+1;k<DNum ;k++)
{
if(data[k]>data[j])
{
temp=data[k];
data[k]=data[j];
data[j]=temp;
}
}
}
}
}

//let all boxes sorted as descending,information stored in dIndex;

bool IsBig(int a,int b)
{
int i=0;
while(i<DNum)
{
if(data[a]>data)
return true;
if(data[a]<data[i])
return false;
i++;
}
return true;
}

void sortB(void)
{
int i,j,temp;
for(i=0;i<BNum;i++)
dIndex[i]=i;
for( i=1;i<BNum;i++)
{
for(j=0;j<i;j++)
{
if( IsBig(dIndex[i],dIndex[j]) )
{
temp=dIndex[i];
dIndex[i]=dIndex[j];
dIndex[j]=temp;
}
}
}
}

bool IsPackable(int a,int b) //if a can be packed into b,return true;
{
int i=0;
while(i<DNum)
{
if(data[a][i]>=data[i])
return false;
i++;
}
return true;
}


void getMaxL(void)
{
int i,j,tempmax;
//init DP;
for(i=0;i<BNum;i++)
{
DP[i][0]=0;
DP[i][1]=-1;
}
maxL=1;
maxLP=0;
DP[0][0]=1;
DP[0][1]=-1;
for(i=1;i<BNum;i++)
{
for(j=0;j<i;j++)
{
tempmax=DP[j][0]+1;
if(tempmax>DP[i][0] && IsPackable(dIndex[i],dIndex[j]))
{
DP[i][0]=tempmax;
DP[i][1]=j;
if(tempmax>maxL)
{
maxL=tempmax;
maxLP=i;
}
}
}
}
}

bool Input(void)
{
int i,j;
while( cin>>BNum>>DNum )
{
for(i=0;i<BNum;i++)
for(j=0;j<DNum;j++)
cin>>data[i][j];
return true;
}
return false;
}

void print(void)
{
cout<<maxL<<endl;


while(DP[maxLP][1]>-1)
{
cout<<(dIndex[maxLP]+1)<<' ';
maxLP=DP[maxLP][1];
}
cout<<(dIndex[maxLP]+1)<<endl;

}

void main(void)
{
#ifndef OJ
freopen("in.txt", "r", stdin);
freopen("outAC.txt", "w", stdout);
#endif

while(Input())
{
sortD();
sortB();
getMaxL();
print();
}

#ifndef OJ
fclose(stdout);
#endif
}

[shamim]

Although I have not verified the input/output, but this problem has a correction program. That is, their could be multiple correct output and both of them will be judged AC.

Please verify whether this is the case with this solution.

[guitarlover]

Hi,
Tks for reply. Anyway, I can not get what correction program means, and why a program with wrong output got accepted. Just help if you can. Tks a lot.

[chunyi81]

First thing though, please specify the problem number in your post next time.

I believe you are referring to problem 103, which has a yellow tick next to the problem. This means that for an input, it is possible to have more than one correct output as shamim stated in his post.

[mf]

Here is the AC code(which produce wrong output for this input)

Output of that code is wrong, I agree.
You should post this in Bugs and suggestions forum and notify the admins. They can add more tests cases for this problem.

[guitarlover]

First thing though, please specify the problem number in your post next time.

I believe you are referring to problem 103, which has a yellow tick next to the problem. This means that for an input, it is possible to have more than one correct output as shamim stated in his post.

Dear Ng Chun Yi,
- I have stated the Problem No in the topic title. Pls check before post.
- It produce a wrong output. It is not a correct one. You can submit and check it carefully before postin. I do so before I post.

P/S: For admin
My first post, so feel free to move to the correct forum. Tks

[guitarlover]

There should be 2 posibilities:
1 - OJ doesn't cover such a test case.
2 - Test multiple output includes wrong output.

My question is that, how can a program produce a wrong result, can be accepted, because it is a simple case. Keep in mind that for this problem, even multiple output is allowed, they should be all correct.

Welcome discussion.

[chunyi81]

Dear Ng Chun Yi,
- I have stated the Problem No in the topic title. Pls check before post.
- It produce a wrong output. It is not a correct one. You can submit and check it carefully before postin. I do so before I post.

Okok... It looks like I need a visit to the optician.

And I agree that the output from that AC program is wrong. My AC program produces the same output as the one you given in your first post.

[guitarlover]

Hee, Just watching too much soccer...
Anyway, maybe I will notify the admin about this problem. I also notice that many people got WA, I dun know whether it is from this error or not...

[rodrigoalveslima]

My code to solve problem 103 is getting Runtime Error. Somebody can help me?

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define MAX 31
#define N_MAX 26

struct celula {
	int dim[N_MAX];
} box[MAX];

int v[MAX];
int marc[MAX];
int G[MAX][MAX];
int count;

int compare (const void * a, const void * b)
{
	return ( *(int*)a - *(int*)b );
}

int cabe (int x, int y, int t)
{
	int c;
	for(c=0;c<t;c++)
		if(box[x].dim[c]>=box[y].dim[c])
			return 0;
	return 1;
}

int dfs (int p, int n)
{
	int l;
	for(l=1;l<=n;l++)
		if(G[p][l]==1 && marc[l]==0) {
			marc[l]=1;
			dfs(l, n);
		}
	v[count]=p;
	count--;
	return 0;
}
			

int main ()
{
	int n, k, i, j, z, lis[MAX], pred[MAX], resp, resp_inic, final[MAX], count_final;
	while(scanf("%d %d", &n, &k)==2) {
		for(i=1;i<=n;i++) {
			for(j=0;j<k;j++)
				scanf("%d", &box[i].dim[j]);
			qsort(box[i].dim, k, sizeof(int), compare);
			for(z=1;z<i;z++) {
				if(cabe(i, z, k)==1) {
					G[i][z]=1;
					G[z][i]=0;
				}
				else if(cabe(z, i, k)==1) {
					G[z][i]=1;
					G[i][z]=0;
				}
				else {
					G[i][z]=0;
					G[z][i]=0;
				}
			}
		}
		for(i=1;i<=n;i++) {
			marc[i]=0;
			lis[i]=1;
			pred[i]=i;
		}
		count=n;
		for(i=1;i<=n;i++) {
			if(marc[i]==0) {
				marc[i]=1;
				dfs(i, n);
			}
		}
		resp=0;
		resp_inic=0;
		for(i=1;i<n;i++) 
			for(j=i+1;j<=n;j++)
				if(G[v[i]][v[j]]==1 && lis[v[j]]<lis[v[i]]+1) {
					lis[v[j]]=lis[v[i]]+1;
					pred[v[j]]=v[i];
					if(lis[v[j]]>resp) {
						resp=lis[v[j]];
						resp_inic=v[j];
					}
				}
		count_final=0;
		printf("%d\n", resp);
		while(pred[resp_inic]!=resp_inic) {
			final[count_final]=resp_inic;
			count_final++;
			resp_inic=pred[resp_inic];
		}
		final[count_final]=resp_inic;
		for(i=count_final;i>=0;i--)
			printf("%d ", final[i]);
		printf("\n");
	}
	return 0;
}

Rodrigo