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

The first step in solving this problem is: if a certain value

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

Now we can decompose the resulting sequences of length

At first sight, it seems that we have a O(

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!

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*. 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_{i}*n*,*m*, and the numbers*a*, one needed to find how many times each element of the original sequence appears in the final sequence._{i}*n*and*m*are up to 10^{5},*a*are up to 10_{i}^{18}.The first step in solving this problem is: if a certain value

*a*is smaller than or equal to the previous value_{i}*a*_{i-1}, then the previous value can be removed, as we will truncate the result of (*i*-1)-st operation to*a*numbers anyway. After repeating this several times, we arrive at a strictly increasing sequence_{i }*a*, which effectively contains those numbers from the original sequence that are smaller than all following numbers._{i}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*. What does it fold to? Let's divide_{m}*a*by_{m}*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*that is less than y, after which it will again transform into several copies of_{j}*a*plus some smaller remainder. By continuing this process, we will have decomposed our initial long sequence_{j }*a*into a few copies of the sequences of length_{m}*a*where_{j}*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*^{2}) 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*. In total, that leads to a running time of O(_{j}*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!

## No comments:

## Post a Comment