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

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

11110 - Equidivisions

Post by Vexorian » Sun Oct 08, 2006 1:33 am

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?

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sun Oct 08, 2006 2:36 am

I also had a lot of trouble with this problem. The trick is that some cells appear twice in the input.

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Sun Oct 08, 2006 7:03 am

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

Code: Select all

ACC   :D 
pleae help me. [/code]
If I will myself do hashing, then who will do coding !!!

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Sun Oct 08, 2006 2:10 pm

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

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

aniket
New poster
Posts: 1
Joined: Wed Oct 04, 2006 11:45 am
Location: On the earth

Post by aniket » Sun Oct 08, 2006 10:51 pm

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

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");
			}


		}
	}

}
Hope any kind helper wish to compile and check the code for rescuing me
bye
Last edited by aniket on Mon Oct 09, 2006 7:01 pm, edited 1 time in total.
I AM THE MASTER OF WA

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Oct 09, 2006 5:34 am

I didn't check that code above, but I got frustrated with this problem, too.

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 changed that to "less than" and it worked - same cell might appear in the description of the *single* partition more than once. I am guessing that is what david meant (I understood it as "same cell can appear in different partitions" - which also might be true).

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Oct 09, 2006 8:04 am

I was really frustrated with this problem in the online contest..

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

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Mon Oct 09, 2006 4:15 pm

I see! A partition is not necessarily going to have n points in each partition input.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Oct 10, 2006 4:00 pm

So what is the fix for this "no problem"-problem :)

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

Post by mrahman » Thu Oct 12, 2006 5:02 am

Hi,
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 like

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; 
	  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"); 
         } 


      } */
   } 

} 
Good Luck!

Sorry for my poor english.
Practice Makes a man perfect

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Thu Oct 12, 2006 6:03 am

My mistake besides of expecting each line to have n pairs was that it was possible for a number to exceed n or be 0 , the problem statement says it clearly, the numbers will be non-negative numbers, never said anything about the numbers being in the correct range.

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

Post by slxst » Mon Oct 16, 2006 2:30 am

Could someone provide tricky test cases?

I checked all the possible flaws here discussed but my code doesn't fall on those. However I still get WA! :evil:

Thanks!

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

Post by mrahman » Wed Oct 18, 2006 5:51 am

Hi slxst,

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
output #

Code: Select all

good
wrong
Hope it will help.
Practice Makes a man perfect

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Wed Oct 18, 2006 6:00 am

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
I strongly doubt that that kind of input come..
My AC program can't handle that..

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Oct 25, 2006 11:33 am

still WA...
mrahman wrote:Hi slxst,

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
output #

Code: Select all

good
wrong
Hope it will help.
i can't understand why the first case is "good".
if theres an invalid cell donate, like 0 0, i'm considering it "wrong"

-----
sorry for my poor english. ('A`)

Post Reply

Return to “Volume 111 (11100-11199)”