A week**7

TopCoder SRM 715 was the first round of May 29 - June 4 week (problems, results, top 5 on the left, my screencast). It was nice to reduce the amount of 3am rounds thanks to my United States trip :)

The medium problem continued the "constructive" trend on TopCoder. You are given four numbers: k, n₁, n₂, n₃. You need to construct a valid Towers of Hanoi configuration that requires exactly k moves to be solved, has n₁ disks on the first rod, n₂ on the second one, and n₃ on the third one.

Yandex.Algorithm 2017 Round 3 wrapped up the week, and also completed the selection of the 25 finalists (problems, results, top 5 on the left, analysis, overall standings). Despite the addition of a marathon round which should theoretically be less correlated with the algorithm rounds, the finalist cutoff just increased more or less proportionally, from 32 points from 3 rounds last year to 40 points from 4 rounds this year. Congratulations to all finalists!

In my previous summary, I have mentioned a problem from Round 2 of the same competition: consider all sequences of balls of k<=15 colors, with exactly a_i<=15 balls of i-th color, and no two adjacent balls of the same color. Let's arrange them in lexicographical order. What is the number of the given sequence s in this order?

Finding the number of s is equivalent to counting the number of sequences coming before s in lexicographical order. Coming before in lexicographical order, in turn, means that some prefix of the such sequence would be equal to the corresponding prefix of s, and the next number will be smaller than the corresponding number of s. That allows us to split our problem into 15 simpler subproblems, each looking like: how many sequences of balls of k colors exist, with exactly b_i<=a_i balls of i-th color, no two adjacent balls of the same color, and the first ball has color less than c, and not equal to d?

Here comes the main idea that I keep forgetting. Let's add balls into our sequence color-by-color. In order to not have adjacent balls of the same color in the end, it suffices to simply remember how many pair of adjacent balls of the same color we have. In other words, having placed some amount of colors, for a total of t balls, we have t+1 positions where the balls of the next color can be placed, and some of those positions are special: we must place at least one ball in that position eventually, to avoid having two adjacent balls of the same color in the final position. We need to remember just the number of special positions, and do not need to remember which ones exactly are special.

When placing a new color which has a_i balls, we iterate over the number m of blocks of consecutive balls of this color we're going to have, and the number p of those blocks that will be inserted into special positions. Now we need to multiply several combination numbers (to choose p special positions, to choose m-p non-special positions, and to split a_i balls into m non-empty blocks), and we also know the new number of special positions which changes by -p+(a_i-m).

Finally, in order to deal with the requirements on the color of the first ball, we can start by processing the colors the first ball can be, and continue with the colors it can't be, and disallow placing balls into the first position on the second stage, which just reduces the number of available non-special positions by one.

Assuming we have k colors and at most a balls of each color, the running time of this approach is a product of:

• k*a for iterating over the position of the first difference,
• k for iterating over colors,
• k*a for iterating over the number of special positions so far,
• a for iterating over the number of blocks we form with the new color,
• a for iterating over the amount of said blocks that go into special positions,

for a total of O(k³a⁴).

Thanks for reading, and check back for the next week's summary!