541 - Error Correction
Moderator: Board moderators
-
- New poster
- Posts: 39
- Joined: Mon Dec 04, 2006 2:18 pm
- Location: Bangladesh(CSE DU)
- Contact:
-
- New poster
- Posts: 39
- Joined: Mon Dec 04, 2006 2:18 pm
- Location: Bangladesh(CSE DU)
- Contact:
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
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.
Try, for example, this input:
It's impossible to restore parity property by changing any one single bit, so you should output "Corrupt".
Code: Select all
3
1 1 1
1 1 1
1 1 1
0
-
- Learning poster
- Posts: 97
- Joined: Fri Aug 22, 2008 10:18 pm
- Location: CSE.SUST.SYLHET
Re: 541 WA
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;
}
Re: 541-error correction --help is wanted
Can you help me with this code ?
I get WA
![:-?](./images/smilies/icon_confused.gif)
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 ;
}
Re: 541-error correction --help is wanted
A little tip:
It is enough to use matrix of bools (in C++ at least), since you have only bits![:)](./images/smilies/icon_smile.gif)
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?
It is enough to use matrix of bools (in C++ at least), since you have only bits
![:)](./images/smilies/icon_smile.gif)
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?
-
- New poster
- Posts: 4
- Joined: Thu Dec 29, 2011 12:03 am
Re: 541-error correction --help is wanted
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:
Test CaseS:
Output:
Any help would be greatly appreciated. Thanks.
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;
}
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
Code: Select all
OK
Change bit (2,3)
Corrupt
Change bit (1,1)
Change bit (1,2)
Corrupt
OK
Corrupt
Corrupt
Corrupt
Corrupt
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 541-error correction --help is wanted
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.
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!
-
- New poster
- Posts: 2
- Joined: Thu Feb 26, 2015 4:29 pm
Re: 541 - Error Correction
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:
![:cry:](./images/smilies/icon_cry.gif)
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);
}
}
}
}
}
-
- New poster
- Posts: 1
- Joined: Thu Feb 18, 2016 11:49 am