You are not logged in. Please login at www.codechef.com to post your questions!

×

ASYA1 - Editorial

PROBLEM LINK :

Contest
Practice

Author : Asim Krishna Prasad
Tester : Rupesh Maity

DIFFICULTY :

EASY

PREREQUISITES :

Binary numbers

PROBLEM :

Given a particular encoding technique, you have to develop the decoding technique. One important detail is that there can be at most one bit error in the encoded message and the received message.Please read the problem statement for detailed explanation of the problem.

EXPLANATION :

The problem is of observation type. If you run some examples by hand on paper or just look closely at the explained example in the question. You can make following important observations :

  • All the bits at position 2i (from right) in the Encoded message, are not part of the original message.
  • All the bits of the original message, (that is the bits at the positions which are not 2i, let us call such positions x) contribute to the formation of all the bits at position 2i such that i-th bit is set in x.
Once you make the following observations, the only problem that remains is to identify the bit which has got error, if any.
Let us say position y has got error, which means the y-th bit got toggled.
Since no other bit other than y has got error, we can check for the consistency of the encoding algorithm on the received message.
To check the consistency we calculate the value of every 2i-th bit, now there are two cases :
  • Case 1 : the calculated value matches the value of 2i-th bit in the received message
    In this case, the conclusion is that i-th bit is not set in y (or else it must have had caused inconsistency at 2i-th bit).
  • Case 2 : the calculated value doesn't match the value of 2i-th bit in the received message
    In this case, the conclusion is that i-th bit is set in y.

The problem is almost solved at this point. You might want to try the problem once again by yourself. For further solution, read on ....
So, the final and most important conclusion from the above observations is that all those 2i-th bits in the encoded message will have error such that i-th bit is set in y. Once you find all those bits which are set in y, you know the position at which the error has occurred.
Once you have detected the position at which the error has occurred, toggle the value at that position and print all the values which are a part of the original message, i.e, all the positions which are not of type 2i.

EXAMPLE :

Let us run our solution algorithm on the given test case :
R = 10111111101011000 .
We have to check the consistency of all the bold bits.

Now value at position 1 : (sum of bits at position 3, 5, 7, 9, 11, 13, 15, 17) % 2
= (1 + 1 + 1 + 1 + 1 + 1 + 0 + 0) % 2
= 6 % 2
= 0

value at position 2 : (sum of bits at position 3, 6, 7, 10, 11, 14, 15) % 2
= (1 + 1 + 1 + 0 + 1 + 1 + 0) % 2
= 5 % 2
= 1

value at position 4 : (sum of bits at position 5, 6, 7, 12, 13, 14, 15) % 2
= (1 + 1 + 1 + 0 + 1 + 1 + 0) % 2
= 5 % 2
= 1

value at position 8 : (sum of bits at position 9, 10, 11, 12, 13, 14, 15) % 2
= (1 + 0 + 1 + 0 + 1 + 1 + 0) % 2
= 4 % 2
= 0

value at position 16 : (sum of bit at position 17) % 2
= 0 % 2
= 0

We find that there is inconsistency at positions 1, 2, and 8. So, the position of the bit with error has 0th, 1st and 3rd bit set, that is : 1011. Thus the position with error is 11.

Toggle the bit at 11th position, we convert the received message to encoded message, which is : 10111111100011000 .

Now extract the original message : 111110001100.

SOLUTION :

Setter's solution

asked 07 Mar '16, 01:06

pakhandi's gravatar image

4★pakhandi
125113
accept rate: 0%

edited 07 Mar '16, 01:17

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,678
×3,763
×832
×184
×23
×1

question asked: 07 Mar '16, 01:06

question was seen: 809 times

last updated: 07 Mar '16, 01:17