A penalty week

The competitive May 14 - May 20 week started with Codeforces Round 483 on Tuesday (problems, results, top 5 on the left, analysis). Problem D turned out to be almost unsolvable, and skipping it was the key to victory. Congratulations to fateice on solving all remaining problems in just under an hour!

TopCoder SRM 734 followed on Thursday (problems, results, top 5 on the left, analysis). The round has feature three relatively standard problems, in particular the last two problems should be good dynamic programming practice.

On Saturday Google Code Jam 2018 Round 2 narrowed the field to just 1000 competitors (problems, results, top 5 on the left, analysis). Getting into the top 1000 does not usually present a big challenge for the top competitors, so they can focus on competing for fun. This time Um_nik was the fastest to solve all problems, but he allowed one incorrect attempt and Gennady.Korotkevich claimed the first place. Congratulations to both!

Yandex.Algorithm 2018 Final Round took place in St Petersburg and online early on Sunday (problems with Yandex login, results, top 5 on the left, my screencast, analysis). The top 2 did not change from the Code Jam round, although this time Gennady has actually left the door wide open by solving the first five problems a lot slower than Um_nik and accumulating some penalty time — Um_nik just needed to get the last problem accepted before the end of the contest, but it did not happen. Congratulations to Gennady on the victory!

The easiest problem of the round, Problem E, required one to locate the number n in a permutation of integers between 1 and n. You are given just the number n and can send queries to learn the permutation. Each query is a number k between 1 and n, and means "increase the number in k-th position in the array by 1". After performing the requested action, the system tells you the number of distinct values in the array (which initially contains the permutation), and you can send the next query which will be applied to the new array (which is not a permutation anymore). You must tell the original location of the number n after at most 50n queries.

And finally, AtCoder Grand Contest 024 wrapped up the week (problems, results, top 5 on the left, my screencast, analysis). This time it was actually me who was the fastest to finish all problems, but I paid the price for the three incorrect attempts. Congratulations to Gennady on the victory!

I found problem F in this round quite educational: you are given a set of strings of length <=20 (possibly all such strings — see the problem statement for the input format that makes it possible to read the input quickly) and a number k. You need to find the longest string that is a subsequence of at least k of the given strings. In case there are many, you need to find the lexicographically smallest one.

Thanks for reading, and check back for more!