11110 - Equidivisions

[razor_blue]

I've tried sample input above, and my code gives the correct answer.
But my code is still WA, does someone know my mistake?

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 150
int n,field[MAX][MAX],flag[MAX][MAX],tot;
void cek(int i,int j,int k)
{
	if(field[i][j]==k)
	{
		if(flag[i][j]==0) 
		{
			tot++; flag[i][j]=1;
		}
		if(i>0&&flag[i-1][j]==0) 	cek(i-1,j,k);
		if(i<n-1&&flag[i+1][j]==0) 	cek(i+1,j,k);
		if(j>0&&flag[i][j-1]==0) 	cek(i,j-1,k);
		if(j<n-1&&flag[i][j+1]==0) 	cek(i,j+1,k);
	}
}
int main()
{
	int i,j,k,jum[MAX],a[MAX],b[MAX],bad;
	char line[1000],*p;
	while(gets(line))
	{
		n=atoi(line);
		if(!n) break;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++) { field[i][j]=flag[i][j]=0; }
		for(k=1;k<n;k++)
		{
			jum[k-1]=0;
			gets(line);
			p=strtok(line," "); i=atoi(p);
			p=strtok(NULL," "); j=atoi(p);
			a[k-1]=i-1;
			b[k-1]=j-1;
			if(i&&j) { field[i-1][j-1]=k; jum[k-1]++; }
			while((p=strtok(NULL," "))!=NULL)
			{
				i=atoi(p); p=strtok(NULL," "); j=atoi(p);
				if(i&&j) { field[i-1][j-1]=k; jum[k-1]++; }
			}
		}
		bad=0;
		for(i=0;i<n-1;i++)
		{
			tot=0;
			cek(a[i],b[i],i+1);
			if(tot!=jum[i]) { bad=1; break; }
		}
		if(bad) printf("wrong\n");
		else printf("good\n");
	}
	return 0;
}

[TimeString]

Finally, I get AC

I use a lot of OLE and get some conclution:
(In one case...)
- A line may not contain exactly 2*N numbers, maybe less than it, maybe more than it. Moreover, it is possible that there are no numbers in this line!! So if you use C or C++, you'd better use gets().
- Although you don't know how many numbers in one line, one thing is sure that there are even numbers.
- All coordinate are available, i.e., the range of all numbers are between 1 to N.
- Two different lines don't contains same coordinates. But be careful, a line may contains same coordinates several times. In this situation, just ignore the repeat one. Don't consider this situation should get "wrong"!!

[baodog]

If there is empty line do you automatically
output "wrong" ?? or ignore this division, and
check if the others are evenly divided? ....
I tried both, and still get WA...
I get Ac on this problem on the PKU site.
anyway, this problem has some nasty inputs added ...
can someone post some critical i/o?
Thanks.

[Robert Gerbicz]

I get Ac on this problem on the PKU site.

I'm very confused about this very easy rated problem. After solving ~20 similar problems on acm uva.
I've downloaded the contest's dataset, containing 11 tests, my program giving the correct answers! However that cases doesn't contain silly inputs: like empty lines or not 2*n numbers in a line or out of range ( 1..n ) numbers.
My algorithm:

1. Check if in a line there are exactly n different correct ( 1<=x,y<=n )pairs that doesn't appear on earlier lines. If this doesn't hold then the answer is wrong. In a line it should be more than one time a pair, it doesn't matter, I count only once if this is a new pair.
2. This also implies that if there is an empty line then the answer is wrong.
3. If there are odd number of numbers in a line then the answer is wrong.
4. Collect coordinates for the n-th set. ( Not in earlier lines )
5. Check if the n sets are continous.
6. If yes then it is good otherwise wrong.

This algorithm gets WA. So what should I do, what's wrong?!

[TimeString]

If there is empty line do you automatically
output "wrong" ??

Yeah, it should print "wrong".

Here are some I/O. Hope it helps.

Input:

Code: Select all

1
2
1 1
2
1 1 1 2
2
1 1 1 2 2 1
2

2
1 1 1 2 1 2
3
1 1 1 2 1 3
2 1 2 2 2 3
3
1 1 1 2     1 3
2 1 2 2     2 3
3
1 1 1 2 2 1
3 3 3 2 2 3
3
1 1 1 2 1 3 1 1 1 2 1 3      
2 1 2 2 2 3 2 1 2 2 2 3        
0

Output:

Code: Select all

good
wrong
good
wrong
wrong
good
good
good
wrong
good

[baodog]

Thanks! Your input is good!
I had simple i/o bug ....
Finally got ac...
It's definitely tricky i/o ....
I didn't realize there could be extra spacing !!

[Robert Gerbicz]

Thanks! Your input is good!
I had simple i/o bug ....
Finally got ac...
It's definitely tricky i/o ....
I didn't realize there could be extra spacing !!

From problem statement:

Code: Select all

Consecutive integers in a line are separated with a single blank character.

So the input is broken. Anyway my original program handle this case ( extra spaces ) and gives the correct answers. Any other tricky input/output ?
For n=1 my program prints good, is it correct?

[Robert Gerbicz]

OK. Finally after about ~30 submissions I got AC. The last error was a silly range error. ( I haven't deleted the whole array ).
The algorithm what I posted is correct and for n=1 the answer is good.
Note that my program also handle the case when some of the coordinate is not positive or >n ( just ignore these cells ).

[rossi kamal]

i am getting tle
here is my code

another problem is that can I consider 2*n+1 inputs in a line or more than one blank in a line?

Code: Select all

//11110
#include<stdio.h>
int main()
{
  
   // freopen("in11110.txt","r",stdin);
	int n;
	
	
	while(scanf("%d",&n) && n!=0 )
	{
		
	    int a[210][210];
		int mark[105][105];
	    int i,j,k=0;
	    int flag=1;     
		
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
	           mark[i][j]=n ;

        for(i=1;i<=n-1;i++)
			for(j=1;j<=2*n;j++)
				scanf("%d",&a[i][j]);
	                    
        for(i=1;i<=n-1;i++)
        {
			
			for(j=1;j<=2*n-1;j+=2)
			{
				int c,d;
				c=a[i][j];
				d=a[i][j+1];
			
				
				mark[c][d]=i;
			
			}	
			
			
		}


        for(i=1;i<=n;i++)
		{	
			for(j=1;j<=n;j++)
			{
				if(mark[i][j]==n)
				{
					a[n][++k]=i;
					a[n][++k]=j;
				

				}	
				
                

			}  
          

		    
        }

        
		
		
		for(i=1;i<=n;i++)
		{
			if(flag==0)
				break;
			for(j=1;j<=(2*n)-1;j+=2)
			{
				
				int e,f;
				e=a[i][j];
				f=a[i][j+1];;

				if(mark[e][f+1]==i||mark[e][f-1]==i||mark[e-1][f]==i||mark[e+1][f]==i )
					flag=1;
				else
				{	
					flag=0;
				    break;
				}
		

			     
			}
            
			
          
		
		}


        if(n==1)
			printf("good");
		
		else {	
			
				if(flag==0)
					printf("wrong");
				else
				printf("good");
		
		}

      
	
	
	
	}
 



	return 0;


}



  

thanks in advance

[calicratis19]

i m disappointed.very very disappointed . i have tried everything i know.countless time wa. pls help.

my alogorithm is following...

1.initial the flag matrix to 0. take the area matrix as string.
2. then i look in nXn grid for areas of partition.
3.i mark the areas which are inside nXn grid with 1.
4.i check if number of areas which are marked with 1 in a particular line is smaller than n. if it is i print wrong.
5.then i run flood fill for the line.
6.if connected areas are smaller than n print wrong.
7.n-1 lines have parsed.then i look for areas with mark ' 0 '.because they have not accessed before,which means they are the nth line.
8.repeat 5 and 6.

Code: Select all

deleted after AC :D  :D .my above algorithm is correct.

[calicratis19]

too bad .. no one is replying..

any guru's or great helpers or anyone ..pls help.

mona doya maya thakla kao ekta reply dan

[Jan]

Your code doesn't handle multiple digits. Check the case.

Input:

Code: Select all

11
1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 
2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 
3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3 11 
4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 4 11 
5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 5 11 
6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 6 11 
7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7 11 
8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8 8 9 8 10 8 11 
9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 9 10 9 11 
10 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 10 11 
0

Output:

Code: Select all

good

Hope it helps.

Note: Next time try to be more patient.

[calicratis19]

many many thanks to jan bhai.i will be patient next time

[phoenix]

WA WA WA
where is the problem ??

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#define max 120
using namespace std;

int array[max][max];
int c;
int global=0;
int size;
void input(int size)
{
	int i,j;
	int m=1;
	int p=size;       

	stack<int>s;
	char line[max];
	int num;
	getchar();

	for(i=1;i<=size;i++)
		for(j=1;j<=size;j++)
			array[i][j]=0;
	size--;
	
	while(size--)
	{
		gets(line);
		stringstream ss(line);
		while(ss>>num)
			s.push(num);
		if(s.empty())
		{
			global=1;
			cout << "wrong" << endl;
			break;
		}
		while(!s.empty())
		{
			int x = s.top();
			s.pop();
			int y = s.top();
			s.pop();
			array[x][y]=m;
		}
		m++;
	}

/*	for(i=1;i<=p;i++)
	{
		for(j=1;j<=p;j++)
			cout << array[i][j];
		cout << endl;
	}*/



}


void ff(int x,int y,int num)
{
	if(array[x][y]==num)
	{
		array[x][y]=-1;
		c++;
		if(array[x-1][y]==num && x-1>=1 && x-1<=size && y>=1 && y<=size)ff(x-1,y,num);
		if(array[x][y-1]==num && x>=1 && x<=size && y-1>=1 && y-1<=size)ff(x,y-1,num);
		if(array[x][y+1]==num && x>=1 && x<=size && y+1>=1 && y+1<=size)ff(x,y+1,num);
		if(array[x+1][y]==num && x+1>=1 && x+1<=size && y>=1 && y<=size)ff(x+1,y,num);
	}
	else
		return ;

}
void check()
{
	int i,j,f=0;
	for(i=1;i<=size;i++)
		for(j=1;j<=size;j++)
		{
			//if(array[i][j]>=1 && array[i][j]<=size)
			if(array[i][j]>=0 && array[i][j]<=size)
			{
				c=0;
				ff(i,j,array[i][j]);
				if(c!=size)f=1;
				break;
			}
		}
		if(f==0)
			cout << "good" << endl;
		else
			cout << "wrong" << endl;

}
int main()
{
//	freopen("in.txt","r",stdin);
	
	while(cin>>size && size!=0)
	{
		global=0;
		input(size);
		if(!global)
		check();
	}
	return 0;
}

[Taman]

One of the worst problem description and judge data set I have ever faced. . .