A squeezing week

The third August week featured TopCoder SRM 697 on Thursday (problems, results, top 5 on the left, analysis). I've wasted most of my time trying to solve the hard problem and couldn't squeeze my approach into the time limit, but matthew99a turned out to be better at squeezing - congratulations!

Later that week, AtCoder Grand Contest 003 has ended with a tiny 16-second margin between the first two places (problems, results, top 5 on the left, analysis).

Problem E "Sequential operations on Sequence" required a few ideas to get both the right asymptotic complexity, and an easy-to-code implementation. 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¹⁸.

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

Tweet