This week in competitive programming

Qualification Round of Facebook Hacker Cup 2015 took place last weekend. There was no direct competition, though, since it lasted for 72 hours and featured three relatively easy problems, and you needed to solve just one to advance to the next round, so people were not competing against one another. It still has a scoreboard (available only after logging in to Facebook), and you can see the top 5 who rushed to solve the problems as soon as they were available on the left, out of 940 contestants who solved all three.

Let's return to problem "Nanobugs" mentioned in the last week's post: you have n (at least 20 and at most 50) coins, some of which are fake. Your friend knows that either a or a+1 coins are fake (a is between 1 and 3, and is given). You know the fake coins exactly, but you don't want to reveal that knowledge to your friend. Instead you want to prove your knowledge to your friend by proving that there are exactly x (either a or a+1) fake coins without revealing the status of any particular coin - neither fake nor real. The only method you can use for your proof is a very limited subset equality testing device: it takes two non-interesecting subsets of coins of the same size, and tells whether both subsets have the same amount of fake coins or not.

I will describe the idea of the solution invented by my teammate Andrey Halyavin. First case is when just 1 coin is fake. In this case the friend knows that there are 1 or 2 fake coins. If the total amount of coins is even, then we can start by comparing one half of all coins with another half, with the result being of course that the two halves are not equal. What does your friend learn from this? One of the halves has all real coins, and another half has either 1 or 2 fakes, but he doesn't know which half, so we haven't yet revealed the status of any particular coin. Now let's continue similar comparisons, i-th comparison putting coins i, i+1, ..., i+n/2 on one side and all remaining coins on the other side. All of them will of course return "not equal" since exactly one coin is fake. Your friend still doesn't learn anything about the status of any particular coin, but the theory that there are 2 fake coins falls apart - since in that case at least one comparison would put them on different sides, and we'd get an "equal" result. So we've successfully convinced the friend that there's just 1 fake coin without revealing anything about any particular coin.

What to do if there's just one fake coin but the total number of coins is odd? It's not hard to see that the task is impossible. Every comparison has to leave at least coin aside. If that comparison returns an "not equal" result, then the coins left aside must be real, since there's just one fake coin, so we will have to reveal their status if we are to prove that there's exactly one fake coin. An if that comparison returns an "equal" result, then the coins participating in the comparison must be real.

Now let's describe a solution for the case where there are either 2 or 4 fake coins (the alternative that we want to disprove is 1 or 3 fake coins). If the total number of coins is even, then the solution is very simple: let's just split all coins into two equal sides, and compare them equal. This obviously means that the total number of fake coins is even, but we haven't revealed anything about the status of any particular coin, so we're done.

Handling the case where the total number of coins is odd is slightly more complex. Let's describe another solution for the case where the total number of coins is divisible by 5 and at least 10. We'll assemble a structure consisting of two "flowers" (pictured on the left): one (x, y) flower and one (y, x) flower. A (x, y) flower contains a center containing x coins, and four petals each containing y coins, for the total of x+4y coins. Similarly, a (y, x) flower contains y+4x coins, so we have 5x+5y coins in total. x and y can be arbitrary positive integers.

Now we'll do 4 comparisons, each comparison will put x+y coins on each side. The left side will be the center of the first flower and one of its petals, and the right side will be the center of the second flower and one of its petals. The resulf of each comparison will be "equal". First, it's not hard to see that we learn that the centers of the flowers contain the same number of fake coins: if one center had more fake coins, then the other flower must have compensated for that in each petal, and we'd get at least 4+1=5 fake coins, and we know we have at most 4. Having seen that, it's not hard to see that the corresponding petals of the flowers also have the same amount of fake coins, since they compare equal modulo the centers which are also equal. But that means that the total number of fake coins is even since we have found a match for every group with the same number of fake coins - and that mean we've proven what we needed to our friend. Note that we have not revealed the status of any particular coin: we have many ways to pick an arbitrary even number of fake coins in the centers and petals.

This solution only works if the total number of coins is divisible by 5, but we also have a solution for the case where the number of coins is divisible by 2, and both of those solutions simply prove that the total number of fake coins is even. So we can just put two such solutions side by side and achieve a solution for any n=5p+2q where p and q are at least 3, and it's not hard to see that any odd number above 20 can be represented in this manner (for example as 15 plus an even number). So we've finally solved the 2 and 4 cases completely.

The only remaining case is 3 fake coins. I will not describe the solution in detail here, but it's conceptually similar to the 2 or 4 case, but instead of proving that the total number of fake coins is even we will prove that it divides evenly by 3, using three flowers with three petals each instead of two flowers with four petals each - two (x, y) flowers and one (y, x) flower.

Thanks for reading, and check back next week! Also please share your impressions about Andrey's solution or the alternative solutions you see in comments.