A diameter week

The May 6 - May 12 week contained TopCoder SRM 758 (problems, results, top 5 on the left, analysis). The hard problem in this round was a nice dynamic programming exercise: you are given two sequences a and b of n<=100 elements each, with each element being an integer between 1 and 100, and an integer s between 1 and the sum of all integers in the two sequences. We will permute each of the sequences, and then start taking numbers in the order a₁, b₁, a₂, b₂, ..., until the sum of the numbers already taken is greater than or equal to s, which will happen after taking a number either from a or from b. In how many of the (n!)² possible choices of the two permutations we reach s after taking a number from a? Return the answer modulo 10⁹+7.

Codeforces Round 559 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). ecnerwala has solved the more difficult problem F, but he lost enough points on the first four problems that mnbvmar could get first place with E. Congratulations to both and also to ainta, the only other contestant to solve five problems!

In my previous summary, I have mentioned two problems. The first one came from AtCoder: two players are playing a game on a tree with 200000 vertices. The players make alternating turns, in one turn a player can choose any vertex as the root of the tree, and then all leaves of the resulting rooted tree are removed (or the root itself if it's the only remaining vertex). The player who has to move after the last vertex has been removed loses the game. Who will win if both players play optimally?

First of all, let's consider the difference between "remove all leaves of a rooted tree" and "remove all leaves of an unrooted tree" operation. It's not very big: the set of leaves is the same, with the possible exception of the root: when we pick a leaf of the unrooted tree as the root, it will not get removed, but all other leaves would. If we pick a non-leaf vertex as the root, then we remove all leaves.

Let's assume for now we never pick a leaf as the root until we have to. The process is then deterministic and can be simulated, but can we do better than plain simulation? It turns out that we can, by using quite typical knowledge about the structure of trees. Each tree has a diameter d, trees with even diameter have one center — a vertex such that its distances to all other vertices are <=d/2, and trees with odd diameter have two centers connected with an edge, such that the entire tree is split into two halves, and the distances from each center to all vertices in its half are <=(d-1)/2. We can now notice that the removal of all leaves decreases the maximum distances to the center(s) by 1, and therefore the diameter of the new tree becomes d-2 (because we can reach any vertex from any other vertex in (d/2-1)+(d/2-1) in the even case, and in (d-1)/2+1+(d-1)/2 in the odd case). We will decrease the diameter by 2 until we reach a tree with 1 or 2 vertices.

Now, what changes when we can pick a leaf as the root? If we pick one end of a diameter as the root, then the diameter will only decrease by 1 (since all its vertices but one will remain). Therefore each player in this game has a choice to decrease the diameter by 1 or by 2, until there are only 1 or 2 vertices remaining, in which case there's no choice anymore. A tree with diameter 0 is winning (since we can make a move, but the opponent can not), a tree with diameter 1 is losing (since only two moves are remaining), a tree with diameter 2 or 3 is thus winning (because we can get to diameter 1 in one move which is a losing position), a tree with diameter 4 is losing, and so on: the losing positions are trees with diameter equal to 1 modulo 3.

This is one of many problems where the understanding of maximum distances on trees through diameters and centers makes the solution possible, so I encourage you to understand the concepts if you haven't done already :)

The second problem was from Codeforces: there are n coins of three different colors, but you don't know which color each coin has. In order to determine that, you have 7 rounds available. In one round, you can choose an arbitrary set of non-intersecting pairs of coins, and you will be told whether the coins in each pair are of the same color or not. After the 7 rounds you need to separate all coins into three groups by color. Can you see how to do it?

We can use the first two rounds to ask about all pairs of adjacent coins (in an arbitrary ordering): in the first round we ask about 1-2, 3-4, 5-6, ..., and in the second round we handle the remaining 2-3, 4-5, 6-7, ... Those answers enable us to split the coins into segments of consecutive coins of the same color, such as: AAABBBBCCDDDEFFF...

We know that A and B are different, and that B and C are different, but we don't know anything about the relation of A and C. So in the next two rounds, we can then compare A-C, B-D, E-G, F-H, ..., and C-E, D-F, G-I, H-J, ...

Now we know that each color is not equal to the previous color, and we know if it's equal to the color before the previous color. Since there are only three colors, this allows us to uniquely determine all colors if we fix the first two colors arbitrarily: a color that is not equal to the color before the previous color is the third color that complements the last two. And we needed just 4 rounds to solve the task out of the allowed 7!

Thanks for reading, and check back for more.