A double Dirichlet week

Google Code Jam 2017 Qualification Round spanned 27 hours over the April 8-9 weekend (problems, results, top 5 on the left, analysis). Excited to see so many participants, and hope you enjoyed the problems!

TopCoder Open 2017 Round 1B took place later on Saturday (problems, results, top 5 on the left). While the problem were a bit on the easy side, xudyh was still very impressive in solving all three in a little over 9 minutes, and adding 200 challenge points to boot. This result has earned him a spot in the official record book, and could've placed him second in this unofficial one had it still been up. Well done!

Open Cup 2016-17 Grand Prix of Two Capitals continued the weekly rush of spring Open Cup rounds (results, top 5 on the left). The interactive problem G "Pigeonhole Principle" was very beautiful, so please try to bear with the long statement :)

Two players are playing a game using a grid with n+1 rows and n columns. Each cell of the grid will contain a 0 or a 1, but the contents of the cells are initially undetermined. The first player, let's call him Dirichlet, can ask questions of form "what is the sum modulo 2 in this subset of cells", for any subset of cells. The second player, let's call him Pigeon, answers the questions - each answer is either 0 or 1. Pigeon can answer questions in any way - for example, he does not have to imagine a concrete grid and use it to compute the answers.

Dirichlet's goal is to get one of the three outcomes:
1) Find a contradiction in Pigeon's answers. More precisely, find a set of questions such that each cell of the grid appears an even number of times in this set, and thus the sum of all answers must be 0 modulo 2, but the sum of Pigeon's answers is 1 modulo 2. One simple case of a contradiction is when he asked about the same set twice and got different answers, but there are much more complicated situations possible.
2) Find two different cells in the same column that he can prove to contain 1. In order to prove that a certain cell contains 1, he can use a set of his questions such that the interesting cell appears an odd number of times in them, and all other cells appear an even number of times in them, and the sum of Pigeon's answers for those questions is 1 modulo 2. One simple way to prove is to ask about the set containing just the interesting cell and receive answer 1, but there are also other ways.
3) Find a row such that he can prove that all its cells contain 0. Proof for each cell must be done similarly to the previous case.

Dirichlet knows that sooner or later one of those three things will happen, since the grid has more rows than columns, and thus it either has a row of 0s or two 1s in the same column. One way to certainly arrive at one of the outcomes is to ask about each cell of the grid separately, using n*(n+1) questions. But Dirichlet wants to win faster: using at most 5*(n+1) questions. Pigeon's goal is to prevent Dirichlet from arriving at one of the three outcomes so fast. You need to implement a program that plays for Dirichlet. n is at most 70.

In the previous summary, I have mentioned a cute Open Cup problem: you are given two numbers n and k. You need to choose the smallest amount of pairs (a,b) such that 1<=a,b<=k for each pair, and such that any sequence of n not necessarily distinct numbers, each between 1 and k, will contain at least one of your chosen pairs as a subsequence.

First of all, consider a sequence of n equal numbers shows that we mush include all k (a,a) pairs in our answer. Moreover, when n>k, we don't need any other pairs thanks to our old friend Dirichlet. But what to do when n<=k? Here one needs to build some intuition first in order to see the right approach.

Let's consider the case n=k. After taking the (a,a) pairs we need to additionally cover all permutations of k numbers. Let's consider one of them: 1,2,...,k. Without loss of generality, we can assume that the pair (1,2) is one of its subsequences present in the answer, so we have at k+1 pairs in our answer now. Is that enough? No, since there exist permutations that do not contain (1,2) as a subsequence. Moreover, there exists a permutation that does not have any common subsequence with our first permutation: k,k-1,...,1. This shows that we need at least k+2 pairs. Which pair should we cover the decreasing permutation with? A natural choice is to use the (2,1) pair. In fact, it's not hard to see that any permutation of k numbers contains either the (1,2) pair or the (2,1) pair as a subsequence, so our k+2 pairs cover all sequences.

Now let's turn to the n=k-1 case. Here the reasoning becomes less formal and more intuitive. Our solution for n=k does not cover sequences that do not contain 1 or 2, for example 2,3,...,k. Let's say this sequence will be covered by (3,4) pair (a pair that contains 2, like (2,3) is less useful since we can replace 2 with 1 and get another uncovered sequence). Again, its reverse will need to be covered, so let's take (4,3) pair as well. Now we have k+4 pairs: (1,1), (2,2), ..., (k,k), (1,2), (2,1), (3,4), (4,3). Dirichlet can easily notice that these k+4 pairs are enough to cover all sequences of length k-1, since any such sequence either contains a repeat, or is missing just one number, and thus either contains both 1 and 2, or contains both 3 and 4.

The cases above have hopefully helped build some intuitive understanding of the problem that allows to generalize the construction to any n: we will split all k numbers into n-1 groups of equal or almost equal size, and will include all pairs of elements from one group into our answer. By the pigeonhole principle, each sequence of length n will contain two elements from the same group, and thus will be covered. As an example, when n=3 and k=5, we will output pairs (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3), (4,5), and (5,4).

A formal proof that this answer is optimal is a bit tedious, so I will just refer you to the Wikipedia article. During the actual contest, the intuition built on simple cases helped this solution to "click" in my head, and thus I submitted it without having a formal proof.

Thanks for reading, and check back soon!