Information Theory #1 - Coins

Information Theory problems are not common and that is why I am writing about them.

They generally consist of two parts : encoding and decoding. It seems to be simple in theory, but problem setters get very creative when adding restrictions that make simple things hard.

Each problem is unique, however there are some aspects that seem to be shared by many problems:

• It is important to know what you need to send
• It relevant to know which information will be available to both the encoder and decoder
• Binary encoding is an efficient way of sending data

The problem we will analyze is Coins from the Practice Section of the International Olympiad in Informatics (IOI 2017 Practice). You may find the problem statement and a place to submit here . I have chosen this one because it is neither too easy nor too hard, so it is the ideal one to start.

A synthesis of the problem statement is : you have a number C (0 <= C < 64) and an array of 64 numbers that are either 0 or 1. In the encoding part, you may change the status of at least one number and at most K numbers of the array. In the decoding part, you receive the array already with the changes and you must answer the number C.

We will focus on the subtasks 3, 4 and 5.

Subtask 3 : K = 64 

The idea of this task is to calculate the number C by the number of 1's in the array. Thus, we flip 0's to 1's until we have C 1's in our array.

Notice that we must always flip at least one coin. So in the case the number of 1's is already equal to C, we need to flip the same coin twice.

Subtask 4 : K = 8

The idea above wastes lots of implicit information that is shared between the encoder and decoder. In order to reduce the number of flips, we must use that information.

Because the position of the numbers of the array do not change, we can use the first 8 coins to send the binary representation of the number C. So we need to flip at most 8 coins, and not 64 like before.

Notice again that in the case the 8 first coins already correspond to the binary encoding of C, we need to flip the same coin twice because we must flip some coin.

Subtask 5 : K = 1

Honestly, I was a bit surprised when the problem asked for a solution that uses only one coin flip. I did not expect such a efficient solution at first. However, after thinking about some bitwise operators, I was able to design an algorithm that did the job.

Firstly , we will need to define a new decoding function for the array. This function may seem a little bit strange at first, but is has a very special property that solves the problem.

Let A be the array we receive. f(A) = i1^i2^…ik where “^” is the bitwise XOR operator and i1,i2 … ik the positions that are “1” on the array. In the case A has no “1”, f(A) = 0.

The first special property is that result of the function is always an integer x such that 0 <= x <= 63.  The second is that when we flip the coin j of A and obtain the array A*, the value f(A*) = f(A)^j , regardless of the state of position j in the array A.

Because 0 <= x <= 63 and 0 <= C <= 63, we can prove that there is an y , 0 <= y <= 63, such that x^y.

This leads to the solution. We calculate the value of f(Aj*) for Aj* identical to A , except for the j-th coin that is flipped, for all 0 <= j <= 63. One of the j's will lead to a configuration whose function value is C, so we return that j as the solution.

A further improvement is that we can know the value of j even quicker. Because of the XOR properties, j = f(A)^C is the position our previous algorithm would find.

The final code could not be simpler.