Sunday, September 11, 2016

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 ai. 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 ai, one needed to find how many times each element of the original sequence appears in the final sequence. n and m are up to 105ai are up to 1018.

The first step in solving this problem is: if a certain value ai is smaller than or equal to the previous value ai-1, then the previous value can be removed, as we will truncate the result of (i-1)-st operation to anumbers anyway. After repeating this several times, we arrive at a strictly increasing sequence ai, 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 am. What does it fold to? Let's divide am by am-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 aj that is less than y, after which it will again transform into several copies of aplus some smaller remainder. By continuing this process, we will have decomposed our initial long sequence am into a few copies of the sequences of length aj where j is less than m, plus some prefix of the original sequence.

Now we can decompose the resulting sequences of length am-1 in the same way, then sequences of length am-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(m2) 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(am) steps, and we can perform each step in O(log(m)) time by doing a binary search for the next suitable aj. In total, that leads to a running time of O(n+m*log(m)*log(am)), 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!

No comments:

Post a Comment