BUTTONS: Getting wa

general
, ,
1

What’s wrong with the output file of this question http://www.codechef.com/problems/BUTTONS/
Its showing wrong anser…
my algo is simple.
1 - XOR the initial and final.
2- try to make the first row 0 by toggling required columns. then toggle rows. make a count (call it c1)
3- try above step for first column make call count as c2
4- check if resulting matrix has all 0’s. If no then print -1
5- check if c1==c2==0. if yes then print 0 (steps)
6- otherwise whichever is smaller print it.
Am i wrong somewhere

2

The total number of button presses must be minimized. Maybe your approach does not satisfy this requirement.

3

this is my code




    #include<stdio.h>
    #define MAXSIZE 1002
    main()
    {	int t,n,i,j;
    	int rows1[MAXSIZE],columns1[MAXSIZE],rows2[MAXSIZE],columns2[MAXSIZE];
    	int rc1,cc1,rc2,cc2,flag1;
    	scanf("%d",&t);
    	while(t--)
    	{	scanf("%d",&n);
    		int init[n][n],final[n][n],ar[n][n];
    		
    		for(i=0;i<n;i++)
    			for(j=0;j<n;j++)
    			scanf("%d",&init[i][j]);
    		
    		for(i=0;i<n;i++)
    			for(j=0;j<n;j++)
    			scanf("%d",&final[i][j]);
    		
    		for(i=0;i<n;i++)
    			for(j=0;j<n;j++)
    			{	ar[i][j]=init[i][j]^final[i][j];
    				final[i][j]=ar[i][j];
    			}
    		// ar is same as final matrix
    		rc1=cc1=rc2=cc2=0;
    	       for(i=0;i<n;i++)
    		{	if(ar[i][0])// reverse row i
    			{	for(j=0;j<n;j++)
    					ar[i][j]^=1;
    				rows1[rc1++]=i;			
    			}
    			
    		}
    		for(j=0;j<n;j++)
    		{	if(ar[0][j])// reverse column j
    			{	for(i=0;i<n;i++)
    					ar[i][j]^=1;
    				columns1[cc1++]=j;
    			}
    		}
    		// other way
    		
    		for(j=0;j<n;j++)
    		{	if(final[0][j])// reverse column j
    			{	for(i=0;i<n;i++)
    					final[i][j]^=1;
    				columns2[cc2++]=j;
    			}
    		}
    			
    		for(i=0;i<n;i++)
    		{	if(final[i][0])// reverse row i
    			{	for(j=0;j<n;j++)
    					final[i][j]^=1;
    				rows2[rc2++]=i;			
    			}
    			
    		}
    		// che k after all toggling if there is a 1 left in the matrix	
         		flag1=0;
    		for(i=0;i<n;i++)
    		{	for(j=0;j<n;j++)
    			{	if(ar[i][j]==1)
    				{	flag1=1;
    					break;
    				}
    			}
    			if(flag1==1)
    			break;
    		}
    		if(flag1)
    		{	printf("-1\n");
    			continue;
    		}
    		if((rc1+cc1)==0&&(rc2+cc2)==0)// no change required
    		{	printf("0\n");
    			continue;
    		}
    		if((rc1+cc1)<(rc2+cc2))
    		{	printf("%d\n",rc1);
    			for(i=0;i<rc1;i++)
    				printf("%d\n",rows1[i]);
    			printf("%d\n",cc1);
    			for(i=0;i<cc1;i++)
    				printf("%d\n",columns1[i]);
    		}
    		else// ifequal give priority to column -row toggling
    		{	printf("%d\n",rc2);
    			for(i=0;i<rc2;i++)
    				printf("%d\n",rows2[i]);
    			printf("%d\n",cc2);
    			for(i=0;i<cc2;i++)
    				printf("%d\n",columns2[i]);
    		}
    	}
    	return 0;
    }
4

you’ll better understand what i meant by “The total number of buttons pressed must be minimized.” if i give you an example of input where your program is failing to achieve the goal :

1
5
0 1 1 1 1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
0 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

the right answer is obviously :

2
0
4
1
0

good luck.

1 Like
5

Thanks cyberax, I found the error. Now i am trying for new algo to cope up with this toggling matrix :slight_smile: