541 - Error Correction

[abdullah<cse du>]

Rushow,

Just change the 2d array to [102][102].
You will get accepted and remove youe accepted code.

ABDULLAH.

[Rushow]

Thank u abdullah<cse du>.
I have got AC.

[abdullah<cse du>]

Rushow,

Cut your accepted code immediately.

ABDULLAH

[abhi]

hi i am unable to figure out the reason for WA.
plz give me some test cases atleast..............
here is my code if u wanna have a look at it

Code: Select all

CODE DELETED AFTER AC :-)

[abhi]

plz hlp me ( (

[mf]

Try, for example, this input:

Code: Select all

3
1 1 1
1 1 1
1 1 1
0

It's impossible to restore parity property by changing any one single bit, so you should output "Corrupt".

[saiful_sust]

WA where is the problem?
can any one help me?
Thanks in advanced.....................

Code: Select all

#include<stdio.h>
#include<stdlib.h>

int a[123][123];
int main()
	{
		int i,n,j,col,row,s,r,p,q;
		
		while(scanf("%d",&n)==1 && n)
		{
			s=0;
			r=0;
			p=0;
			q=0;
			for(i=0;i<n;i++)
			{
				for(j=0;j<n;j++)
				{
					scanf("%d",&a[i][j]);
				}
			}
			
			for(i=0;i<n;i++)
			{
				s=0;
				r=0;
				for(j=0;j<n;j++)
				{
					s=s+a[i][j];
					r=r+a[j][i];					
				}								
				if(s%2==1)
				{
					p++;
					row=i;
				}
				if(r%2==1)
				{
					q++;					
					col=i;					
				}
				if(p>=2 || q>=2)
					break;
			}
			
			if(p==0 && q==0)
				printf("OK\n");	
			
			else if(p==1 && q==1)
				printf("Change bit (%d,%d)\n",row+1,col+1);
			
			else
				printf("Corrupt\n");
		}
		return 0;
	}

[dewsworld]

Can you help me with this code ?
I get WA

Code: Select all

#include <stdio.h>

int   main()
{
//freopen("in.txt", "rb", stdin );

    int     input ;
    int     i, j ;
    bool    map[100][100] ;
    bool    vuaRow[100] ;
    bool    vuaCol[100] ;
    int     count ;

    while( scanf("%d", &input) )
    {
        if( input == 0 )
            break ;

        for( i = 0 ; i < input ; i++ )
            for( j = 0 ; j < input ; j++ )
                scanf("%d", &map[i][j] ) ;

        for( i = 0 ; i < input ; i++ )
            vuaRow[i] = vuaCol[i] = 0 ;

        for( i = 0 ; i < input ; i++ )
        {
            count = 0 ;

            for( j = 0 ; j < input ; j++ )
            {
                if( map[i][j]== 1)
                    ++count ;

                if( count%2 == 0 )
                    vuaRow[i] = 1 ;   // even parity
                else
                    vuaRow[i] = 0 ;   // odd parity
            }
        }

        for( j = 0 ; j < input ; j++ )
        {
            count = 0 ;

            for( i = 0 ; i < input ; i++ )
            {
                if( map[i][j] == 1 )
                    ++count ;
            }

            if( count%2 == 0 )
                vuaCol[j] = 1  ;    // even parity

            else
                vuaCol[j] = 0  ;    // Odd parity
        }

        for( i = 0 ; i < input ; i++ )
            if( vuaRow[i] != 1 )
                break ;

        for( j = 0 ; j < input ; j++ )
            if( vuaCol[j] != 1 )
                break ;

        if( i == input && j == input )
            printf("OK\n") ;


        if( (i == input && j != input) || ( i!= input&&j==input ) )
            printf("Corrupt\n") ;

        if( i!= input && j!= input )
        {
            printf("Change bit (%d,%d)\n", i+1, j+1) ;

        }
    }

    return 0 ;
}

[valkov]

A little tip:
It is enough to use matrix of bools (in C++ at least), since you have only bits
I was wondering is there any other way to solve this problem aside of the brute force approach i.e. how can one find if parity rule is not met?

[ahsanalishahid]

Hi! I have been trying this problem for a while now But I am getting WA for this problem. I have passed different test cases.
Here is the code:

Code: Select all

#include <iostream>
#include <cstdio>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cctype>
#include<iomanip>
#include <locale>

using namespace std;

bool isEvenRow(vector<bool> &row)
{
	int sum = 0;
	for (int i = 0; i < row.size(); i++)
		if(row[i])
			sum++;
	if(sum == 0 || sum %2 == 0 )
		return true;
	return false;
}
int main()
{
	int order;
	int x;
	while(cin >> order){
		if(order== 0)
			break;
		vector< vector<bool> > matrix(order, vector<bool>(order) );
		vector<bool> rowCheck(order),columnCheck(order);
		vector<bool> col(order);
		
		for (int i = 0; i < order; i++){
			for (int j = 0; j < order; j++){
				cin >> x;
				matrix[i][j] = x;
			}
		}
		for (int row = 0; row < order; row++){
			for (int cols = 0; cols < order; cols++)
				col[cols] = matrix[cols][row];
			columnCheck[row] = isEvenRow( col );
		}
		for (int i = 0; i < order; i++)
		{
			rowCheck[i] = isEvenRow(matrix[i]);
		}
		
		//  if OK
		bool isOK= true;
		for (int i = 0; i < order; i++){
			if(!columnCheck[i] || !rowCheck[i] ){
				isOK = false;
				break;
			}
		}
		int row=0,column=0;
		for (int i = 0; i < order; i++){
			if( !columnCheck[i])
				row++;
			if( !rowCheck[i])
				column++;
		}
		if( isOK )
			cout << "OK" << endl;
		else if( row  == column && column == 1 ){
				//change bit
			bool f = false;
			for (int i = 0; i < order; i++){
				for (int j = i; j < order; j++)
					if( !rowCheck[i] && !columnCheck[j] ){
						cout << "Change bit ("<< i+1 << ","<<j+1<<")"<<endl;
						f=true;
						break;
					}
					if(f) 
						break;
			}
		}
		else
			cout << "Corrupt" << endl;	
		
	}
	return 0;
}

Test CaseS:

Code: Select all

4
1 0 1 0
0 0 0 0
1 1 1 1
0 1 0 1
4
1 0 1 0
0 0 1 0
1 1 1 1
0 1 0 1
4
1 0 1 0
0 1 1 0
1 1 1 1
0 1 0 1
1
1
2
1 0
1 1
2
1 0
0 1
1
0
5
1 0 1 1 0
1 1 1 0 0
1 1 1 0 0
0 0 1 0 1
0 1 1 0 1
8
1 0 1 0 0 1 0 0
1 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0
1 0 0 0 1 0 0 0
0 0 1 0 0 1 1 1
0 0 1 0 0 1 1 1
0 1 1 0 0 1 0 1
0 1 0 1 1 0 0 0
8
0 0 1 0 0 0 1 1
1 0 0 1 1 0 0 1
1 1 1 0 1 1 0 1
1 0 1 1 1 0 1 0
1 0 1 0 0 0 0 0
0 1 0 0 1 1 1 1
1 1 1 0 1 1 1 1
0 1 1 0 1 1 1 0
8
1 0 0 1 1 0 1 1
0 1 1 0 1 0 0 1
1 0 0 1 0 1 1 0
1 1 0 0 1 1 0 0
0 1 0 1 1 0 1 0
0 1 1 0 1 1 1 0
0 0 0 1 0 0 1 0
0 1 0 1 0 1 1 1
0

Output:

Code: Select all

OK
Change bit (2,3)
Corrupt
Change bit (1,1)
Change bit (1,2)
Corrupt
OK
Corrupt
Corrupt
Corrupt
Corrupt

Any help would be greatly appreciated. Thanks.

[brianfry713]

From uhunt:
Bettedaniel> ahsanalishahid try to think about constraints. You can simplify the problem quite a lot. Think about the properties of the grid if you're in the different cases for example if you can change 1 bit to make it OK, what does the grid look like then.

[BISHALBISWAS]

i m getting WA with this problem so much times ....need some critical test cases for this problem...thnx in advance...

my code is here:

Code: Select all

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int arra[201][201];
	int n,count,kount,i,j,p,c,p1,k,cnt,a,b,a1,b1,flag,knt,mark,a2,b2;
	while(scanf("%d",&n)==1)
	{
		if(n==0)
		return 0;
		
		cnt=0,flag=0,mark=0,knt=0,c=0;
		for(i=0;i<n;i++)
		{
			count=0;
			for(j=0;j<n;j++)
			{
				scanf("%d",&arra[i][j]);
				if(arra[i][j]==1)
				count++;
				else if(arra[i][j]==0)
				{
					c++;
					a2=i+1,b2=j+1;
				}
			    
			}
				if(count%2!=0)
			{
				cnt++;
				if(cnt>1)
				{
					flag=1;
				}
				else
				{
					p1=count;
					for(j=0;j<n;j++)
					if(arra[i][j]==1)
					{
						b=j;
						break;
					}
					a=i+1;
					b++;
				}
			    
				
			}
			
		}
	
		if(flag==1)
		printf("Corrupt\n");
		else
		{
			for(j=0;j<n;j++)
			{
				kount=0;
			for(i=0;i<n;i++)
			{
				if(arra[i][j]==1)
				kount++;
			}
			if(kount%2!=0)
			{
				knt++;
				if(knt>1)
				{
					mark=1;
					break;
				}
				else if(knt==1)
				{
					p=kount;
					for(k=0;k<n;k++)
					if(arra[k][j]==1)
					{
						a1=k;
						break;
					}
					a1++;
					b1=j+1;
				}
			    
				
			}	
			}
		if(mark==1)
		printf("Corrupt\n");
		else if(cnt==0 and knt==0)
		printf("OK\n");
		else if(knt==1 and cnt==1)
		{
			if(p1>p)
			printf("Change bit (%d,%d)\n",a1,b1);
			else if(p1<p)
			printf("Change bit (%d,%d)\n",a,b);
			else
			{
				if(c==1)
	         printf("Change bit (%d,%d)\n",a2,b2);
	         else
	         printf("Change bit (%d,%d)\n",a,b);
			}
			
		}
			
		}
		
	}
	
}

[sajal_khan]

why i got wA ??

my solution: https://ideone.com/38uSAy

need some critical test cases.....