## 11110 - Equidivisions

**Moderator:** Board moderators

### 11110 - Equidivisions

This one gave me a lot of trouble in the contest, it seemed really easy but I couldn't stop getting a WA, and even reread the prompt finding out things I skipped, can anyone give me some tricky input/output samples I could try on my algorithm?

ok my tle is gone by concidering that fact....

but now WA...

i used union by rank method to make sets of each number....

if the number of elemnts in each set is not n then wrong...

but i m getting WA...

here is the code...

pleae help me. [/code]

but now WA...

i used union by rank method to make sets of each number....

if the number of elemnts in each set is not n then wrong...

but i m getting WA...

here is the code...

Code: Select all

```
ACC :D
```

If I will myself do hashing, then who will do coding !!!

That's broken, cause the statement says that the input is a partition of the matrix, then that shouldn't happen, thanks though.david wrote:I also had a lot of trouble with this problem. The trick is that some cells appear twice in the input.

Edit: Now that I think about it, my alg should be able to resist that kind of input. I also tested with repeated cells and it was giving the correct answer

i cant find why wa

my algo is just simple

just cover all by default

than collect all the partition with their relative number

and then check each partition from the begining cell if it contains the given number of cells adajacent to it or not

here goes my code
Hope any kind helper wish to compile and check the code for rescuing me

bye

my algo is just simple

just cover all by default

than collect all the partition with their relative number

and then check each partition from the begining cell if it contains the given number of cells adajacent to it or not

here goes my code

Code: Select all

```
#include<stdio.h>
long mat[105][105],total_number,total[105],no_x[105],no_y[105],num;
int check(long x,long y,long sym)
{
if(mat[x][y]!=sym)
return 0;
total_number++;
mat[x][y]=-1;
if(x-1>=1)
check(x-1,y,sym);
if(x+1<=num)
check(x+1,y,sym);
if(y-1>=1)
check(x,y-1,sym);
if(y+1<=num)
check(x,y+1,sym);
return 0;
}
void main()
{
long i,j,k,x,y,p,q,temp_count;
char c;
while(scanf("%ld",&num),num!=0)
{
for(i=1;i<=num;i++)
for(j=1;j<=num;j++)
mat[i][j]=1;
for(i=2,p=0;i<=num;i++)
{
scanf("%ld%c",&x,&c);
k=0;
temp_count=1;
while(c==' ')
{
scanf("%ld%c",&y,&c);
temp_count++;
if(temp_count==2)
{
if(mat[x][y]!=1)
p=1;
mat[x][y]=i;
no_x[i]=x;
no_y[i]=y;
k++;
temp_count=0;
}
else if(temp_count==1)
{
x=y;
}
}
total[i]=k;
}
if(p==1)
{printf("wrong\n");continue;}
for(i=2,p=1;i<=num;i++)
{
total_number=0;
check(no_x[i],no_y[i],i);
if(total_number!=total[i])
{p=0;printf("wrong\n");break;}
}
if(p==1)
{
//{p=0;printf("wrong\n");break;}
for(i=1,q=0;i<=num;i++)
{ for(j=1;j<=num;j++)
{
if(mat[i][j]==1)
{q=1;break;}
}
if(q==1)
break;
}
if(q==0)
printf("good\n");
else
{
no_x[1]=i;no_y[1]=j;
total[1]=0;
for(i=1,q=0;i<=num;i++)
for(j=1;j<=num;j++)
if(mat[i][j]==1)
total[1]++;
total_number=0;
check(no_x[1],no_y[1],1);
if(total_number!=total[1])
printf("wrong\n");
else
printf("good\n");
}
}
}
}
```

bye

Last edited by aniket on Mon Oct 09, 2006 7:01 pm, edited 1 time in total.

I AM THE MASTER OF WA

My mistake was that I had a line like:

Code: Select all

```
// if not exactly n pairs of numbers on a line, it's wrong
if (st.countTokens() != 2 * n) ok = false;
```

I also assumed

**if ( v.size() != 2*n ) ok = false**.

And another thing: there were more than one value with the same coordinate... now, which do u consider??? General coding would tend to consider that last one as it would overwrite the earlier ones and it did work... but there is no clear explanation as to why we have to consder the last one.

Poorly written problemstatement....

Hi,

aniket, Your approach is good. But your Input taking method failed you to accept this code. Try to use
Good Luck!

Sorry for my poor english.

aniket, Your approach is good. But your Input taking method failed you to accept this code. Try to use

**gets()**function instead of**scanf()**function and then parse the integer from the string. and you could simplify your code likeCode: Select all

```
#include<stdio.h>
long mat[105][105],total_number,total[105],no_x[105],no_y[105],num;
int check(long x,long y,long sym)
{
if(mat[x][y]!=sym)
return 0;
total_number++;
mat[x][y]=-1;
if(x-1>=1)
check(x-1,y,sym);
if(x+1<=num)
check(x+1,y,sym);
if(y-1>=1)
check(x,y-1,sym);
if(y+1<=num)
check(x,y+1,sym);
return 0;
}
void main()
{
long i,j,k,x,y,p,q,temp_count;
char c;
while(scanf("%ld",&num),num!=0)
{
for(i=1;i<=num;i++)
for(j=1;j<=num;j++)
mat[i][j]=1;
total[1] = num*num; //add this line
for(i=1;i<=num;i++)
{
no_x[i] = -1;
no_y[i] = -1;
}
for(i=2,p=0;i<=num;i++)
{
scanf("%ld%c",&x,&c);
k=0;
temp_count=1;
while(c==' ')
{
scanf("%ld%c",&y,&c);
temp_count++;
if(temp_count==2)
{
//remove this
/*if(mat[x][y]!=1)
p=1; */
mat[x][y]=i;
no_x[i]=x;
no_y[i]=y;
k++;
temp_count=0;
}
else if(temp_count==1)
{
x=y;
}
}
total[i]=k;
total[1]-=k; //add this line
}
//remove this
/*if(p==1)
{printf("wrong\n");continue;} */
// Add below's code for initialize
p=0;
for(i=1;i<=num && !p;i++)
for(j=1;j<=num && !p;j++)
{
if( mat[i][j]==1){no_x[1] = i; no_y[1] = j; p = 1;}
}
// End
for(i=1,p=1;i<=num;i++)
{
if(no_x[i]!=-1 && no_y[i]!=-1) // Add this checking
{
total_number=0;
check(no_x[i],no_y[i],i);
if(total_number!=total[i])
{p=0;printf("wrong\n");break;}
}
}
if(p)printf("good\n"); //add this output line
//remove this
/*
if(p==1)
{
//{p=0;printf("wrong\n");break;}
for(i=1,q=0;i<=num;i++)
{ for(j=1;j<=num;j++)
{
if(mat[i][j]==1)
{q=1;break;}
}
if(q==1)
break;
}
if(q==0)
printf("good\n");
else
{
no_x[1]=i;no_y[1]=j;
total[1]=0;
for(i=1,q=0;i<=num;i++)
for(j=1;j<=num;j++)
if(mat[i][j]==1)
total[1]++;
total_number=0;
check(no_x[1],no_y[1],1);
if(total_number!=total[1])
printf("wrong\n");
else
printf("good\n");
}
} */
}
}
```

Sorry for my poor english.

Practice Makes a man perfect

Hi slxst,

Try this

input #
output #

Hope it will help.

Try this

input #

Code: Select all

```
2
1 2 0 0
5
0 0 1 2 1 3 3 2 2 2
2 1 4 2 4 1 5 1 3 1 3
4 5 5 2 5 3 5 5 5 4
2 5 3 4 3 5 4 3 4 4
0
```

Code: Select all

```
good
wrong
```

Practice Makes a man perfect

I strongly doubt that that kind of input come..mrahman wrote: Hi slxst,

Try this

input #Code: Select all

`5 0 0 1 2 1 3 3 2 2 2 2 1 4 2 4 1 5 1 3 1 3 4 5 5 2 5 3 5 5 5 4 2 5 3 4 3 5 4 3 4 4`

My AC program can't handle that..

i can't understand why the first case is "good".mrahman wrote:Hi slxst,

Try this

input #output #Code: Select all

`2 1 2 0 0 5 0 0 1 2 1 3 3 2 2 2 2 1 4 2 4 1 5 1 3 1 3 4 5 5 2 5 3 5 5 5 4 2 5 3 4 3 5 4 3 4 4 0`

Hope it will help.Code: Select all

`good wrong`

if theres an invalid cell donate, like 0 0, i'm considering it "wrong"

-----

sorry for my poor english. ('A`)