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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Mar 12, 2006 4:04 am

"not" is a restricted name.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

alltoucher
New poster
Posts: 2
Joined: Sat Mar 11, 2006 8:39 pm
Contact:

Post by alltoucher » Sun Mar 12, 2006 11:49 am

Krzysztof Duleba wrote:"not" is a restricted name.
You are right!!!! Thanks!!!

prodigyt
New poster
Posts: 3
Joined: Sun Apr 30, 2006 6:35 pm

#103 - plz test my input

Post by prodigyt » Sun Apr 30, 2006 6:48 pm

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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Mon May 01, 2006 6:51 am

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
New poster
Posts: 3
Joined: Sun Apr 30, 2006 6:35 pm

gr8 thx

Post by prodigyt » Mon May 01, 2006 4:19 pm

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

guitarlover
New poster
Posts: 5
Joined: Thu Jun 15, 2006 6:57 pm

103 Funny Judge Problem

Post by guitarlover » Thu Jun 15, 2006 7:08 pm

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. :D

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
}

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Fri Jun 16, 2006 7:54 am

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
New poster
Posts: 5
Joined: Thu Jun 15, 2006 6:57 pm

Post by guitarlover » Fri Jun 16, 2006 10:59 am

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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Fri Jun 16, 2006 2:44 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Jun 16, 2006 4:57 pm

guitarlover wrote: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
New poster
Posts: 5
Joined: Thu Jun 15, 2006 6:57 pm

Post by guitarlover » Fri Jun 16, 2006 5:10 pm

chunyi81 wrote: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
New poster
Posts: 5
Joined: Thu Jun 15, 2006 6:57 pm

Post by guitarlover » Fri Jun 16, 2006 5:41 pm

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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sat Jun 17, 2006 5:49 am

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. :oops:

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
New poster
Posts: 5
Joined: Thu Jun 15, 2006 6:57 pm

Post by guitarlover » Sun Jun 18, 2006 8:14 pm

Hee, Just watching too much soccer... :D
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
New poster
Posts: 1
Joined: Thu Jun 29, 2006 10:43 pm

103 - Runtime Error

Post by rodrigoalveslima » Thu Jun 29, 2006 10:47 pm

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

Post Reply

Return to “Volume 1 (100-199)”