541 - Error Correction

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

Moderator: Board moderators

abdullah<cse du>
New poster
Posts: 39
Joined: Mon Dec 04, 2006 2:18 pm
Location: Bangladesh(CSE DU)
Contact:

Post by abdullah<cse du> » Sat Mar 24, 2007 6:29 am

Rushow,

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

ABDULLAH.

Rushow
New poster
Posts: 14
Joined: Sat Oct 14, 2006 4:09 pm
Location: Dhaka,Bangladesh

Post by Rushow » Sat Mar 24, 2007 8:25 pm

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

abdullah<cse du>
New poster
Posts: 39
Joined: Mon Dec 04, 2006 2:18 pm
Location: Bangladesh(CSE DU)
Contact:

Post by abdullah<cse du> » Sat Mar 24, 2007 8:46 pm

Rushow,

Cut your accepted code immediately.

ABDULLAH

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

Post by abhi » Tue Jun 19, 2007 7:19 pm

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 :-)
Last edited by abhi on Fri Jun 22, 2007 6:04 pm, edited 1 time in total.

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

Post by abhi » Fri Jun 22, 2007 8:01 am

plz hlp me :(( :((

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Jun 22, 2007 8:17 am

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
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 541 WA

Post by saiful_sust » Wed Sep 10, 2008 9:58 pm

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
New poster
Posts: 12
Joined: Fri Aug 13, 2010 11:52 am

Re: 541-error correction --help is wanted

Post by dewsworld » Sat Aug 28, 2010 8:23 am

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
New poster
Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

Re: 541-error correction --help is wanted

Post by valkov » Mon Dec 20, 2010 6:43 pm

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
New poster
Posts: 4
Joined: Thu Dec 29, 2011 12:03 am

Re: 541-error correction --help is wanted

Post by ahsanalishahid » Sun Nov 24, 2013 8:36 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 541-error correction --help is wanted

Post by brianfry713 » Mon Nov 25, 2013 8:13 pm

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.
Check input and AC output for thousands of problems on uDebug!

BISHALBISWAS
New poster
Posts: 2
Joined: Thu Feb 26, 2015 4:29 pm

Re: 541 - Error Correction

Post by BISHALBISWAS » Fri Mar 27, 2015 5:01 pm

i m getting WA with this problem so much times :cry: ....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
New poster
Posts: 1
Joined: Thu Feb 18, 2016 11:49 am

Re: 541 - Error Correction

Post by sajal_khan » Thu Feb 18, 2016 12:13 pm

why i got wA ?? :(

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

need some critical test cases.....

Post Reply

Return to “Volume 5 (500-599)”