A Reichenbach week

The fourth August week has marked the start of the Petrozavodsk training camp, and with it came newly traditional AIM Tech Round 3 (problems, results, top 5 on the left). Quite fittingly, the winner was present in Petrozavodsk - congratulations Um_nik!

On Saturday evening TopCoder Open 2016 Round 3B has selected four more contestants for the onsite round in Washington (problems, results, top 5 on the left). The 1000-pointer did not give this time, and thus the key was in solving the 500-pointer fast. The challenge phase did not affect the top four - congratulations to rng_58, Um_nik, scott_wu and Enot on qualifying!

In my previous summary, I've mentioned an interesting AtCoder problem. Initially, one was given a sequence of length n. Then m transformations were applied. After the i-th transformation the new length of the sequence became a_i. If the new length was shorter than the current length, the sequence was simply truncated. If the new length was longer than the current length, then we repeated the current sequence periodically to get to the new length. Given n, m, and the numbers a_i, one needed to find how many times each element of the original sequence appears in the final sequence. n and m are up to 10⁵, a_i are up to 10¹⁸.

The first step in solving this problem is: if a certain value a_i is smaller than or equal to the previous value a_i-1, then the previous value can be removed, as we will truncate the result of (i-1)-st operation to a_i numbers anyway. After repeating this several times, we arrive at a strictly increasing sequence a_i, which effectively contains those numbers from the original sequence that are smaller than all following numbers.

The next idea is to look at this problem from the end: instead of unfolding the short sequence into a long one, we will fold the long one. We start with one long sequence of length a_m. What does it fold to? Let's divide a_m by a_m-1, and get the quotient x and the remainder y. Then we get x copies of the sequence at step m-1, and one more copy of its prefix of length y. What will happen to this prefix of length y later? It will stay unchanged until we reach some a_j that is less than y, after which it will again transform into several copies of a_j plus some smaller remainder. By continuing this process, we will have decomposed our initial long sequence a_m into a few copies of the sequences of length a_j where j is less than m, plus some prefix of the original sequence.

Now we can decompose the resulting sequences of length a_m-1 in the same way, then sequences of length a_m-2, remembering how many copies of each length we have, until we've left with just a collection of prefixes (with counts) of the original sequence, which allows us to compute the answer easily.

At first sight, it seems that we have a O(m²) solution since each length decomposes into some set of smaller lengths. However, we can note that the remainder y decreases at least twice in each step, so we have at most log(a_m) steps, and we can perform each step in O(log(m)) time by doing a binary search for the next suitable a_j. In total, that leads to a running time of O(n+m*log(m)*log(a_m)), where the O(n) part is for computing and printing the answer.

A beautiful fact is that, despite such fancy complexity, the solution itself is very simple and easy to code, as it only uses arrays as data structures, and simple binary search as the most advanced algorithm.

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