## 11110 - Equidivisions

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

razor_blue
New poster
Posts: 27
Joined: Mon Nov 27, 2006 4:44 am
Location: Indonesia
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
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am
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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### still get WA

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: still get WA

baodog wrote: 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
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

### Re: still get WA

baodog wrote: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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### Thanks!

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: Thanks!

baodog wrote: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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
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
New poster
Posts: 14
Joined: Mon Sep 03, 2007 10:11 am
Contact:
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
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

### Re: 11110 - Equidivision

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.``
Last edited by calicratis19 on Sat May 09, 2009 7:46 am, edited 3 times in total.
Heal The World

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

### Re: 11110 - Equidivision

too bad .. no one is replying..

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

mona doya maya thakla kao ekta reply dan
Heal The World

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

### Re: 11110 - Equidivision

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.
Ami ekhono shopno dekhi...
HomePage

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

### Re: 11110 - Equidivision

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

phoenix
New poster
Posts: 2
Joined: Sun May 23, 2010 8:19 am

### Re: 11110 - Equidivision

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
New poster
Posts: 32
Joined: Sun Oct 11, 2009 8:59 pm
Location: Southeast University

### Re: 11110 - Equidivision

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