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