Internet Problem Solving Contest

IPSC 2018

Solution to Problem H – Hats of various colors

In the easy subproblem, one simple strategy is to seat everyone in a loop, and have everyone raise their hand if their right neighbor’s color is red, and then say red if their left neighbor raised their hand and blue otherwise. While implementing it, remember that colors are 1 and 2, hands are true and false, and you can’t mix them (Lua doesn’t allow doing arithmetic on booleans, and not 1 and not 2 are both false).

In the hard subproblem, we need something almost optimal. Every prisoner receives N − 1 bits of information – the raised hands of the other prisoners. (Seeing their hats doesn’t tell you anything about your own hat.) So the maximum number of colors you can theoretically distinguish with is 2N − 1. To make that happen, everyone must make full use of their raised hand – it must give information to every other prisoner.

Let’s convert every color into an N − 1-bit binary number between 0 and 2N − 1 − 1, inclusive. When we split those numbers into bits, we can think of the full state as a two-dimensional binary array of N rows (the prisoners) and N − 1 columns (the individual bits of each prisoner’s hat color). Every prisoner sees the whole array except for their own row.

The job of the first N − 1 prisoners will be to tell everyone about the i-th column. They can count the XOR of all the visible bits in their column and send that to everyone else. When you see whether prisoner 1 raised their hand, and combine it with prisoner 1’s own first bit, it will tell you the xor of the whole first column. XOR that with the rows your can see, and it will tell you whether your own first bit is 0 or 1.

The only remaining problem is how everyone can determine their own value in their own column. That’s the only missing bit. The final N-th prisoner can send everyone the XOR of all the bits they can see, which allows everyone to compute the XOR of all bits in the whole table, and since they already know all the bits except one, that will tell them its value.