ACM (UVa): 541


Data type:
Integer

Explanation:
Find the summation of each row and column individually. If All summation is Even then output: OK

or, Find the corrupted row and column. Then output: Change bit (row,column)

Now,
a) if more than one row r corrupted or
more than one column r corrupted then output: Corrupt

b) if one row and one column corrupted but there is no common bit then output: Corrupt.

It’s an Ad-hoc problem so u can use any other algorithm while it’s produce correct output.
But remember, Parity property can be established iff, only one row and only column corrupted and these two have a common bit.

Critical input:
4
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
4
1 1 1 1
0 0 0 0
1 1 1 1
0 0 1 0
4
1 0 0 0
0 0 0 0
0 0 1 1
0 0 1 1
0
Critical output:
Corrupt
Change bit (4,3)
Change bit (1,1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s