A 25+25+50+10 week

TopCoder SRM 661 took place very early on Friday after a mostly calm week (problems, results, top 5 on the left, discussion). One of the highlights of the round is the screencast by subscriber where he has also thought aloud and recorded his voice - check it out if you understand Russian! When solving a problem, it's always helpful to discuss it with somebody, and in many cases simply explaining yourself in words helps understand the solution better and improve it - so it might be that intentionally telling the thoughts loudly actually leads to better results! Definitely need to try this out myself.

Yandex.Algorithm 2015 Round 2.2 gave contestants the final chance to get into the top 25 in overall selection results (problems, results, top 5 on the left, overall selection results, discussion). Unlike the previous round, where the best result with at least two blind submissions was 20th place, this one was not so brutal and Jacob Dlougach has appropriately used the time bonus to claim fourth place. Still, places 1-3 and 5-16 have at most one blind submission each, suggesting that this problemset, authored by GlebsHP, also had a lot of tricks. I wonder if the problemsetter for the final round will be revealed in advance - it seems that this can significantly affect the strategy choices.

Google Code Jam 2015 Round 3 has chosen another top 25, this time to fly to Seattle (problems, results, top 5 on the left, discussion). The intersection between this top 25 and the Yandex one is just 7 people: tourist, iwi, vepifanov, dzhulgakov, AngryBacon, ishraq and qwerty787788 - hope I didn't forget anybody - the intersection is small probably due to the difference in competition formats, the task types, and just to the natural randomness.

The problems presented quite different types of challenges, but here's a particularly nice one. You are standing on a line in point 0 and can run at speed v, and there are n quail running away from you, i-th quail at point p_i (can be positive or negative) running away at speed v_i. What's the smallest time required to catch all quail? n is up to 500.

The two approaches that come to mind for such problems are greedy algorithms and dynamic programming. But it's not clear where would the greedy optimality property come from, and the number of possible states for DP seems exponential - we need to remember which quail we've already caught. Can you see which one of those ideas actually works?

Russian Code Cup 2015 Elimination Round was a bit more generous and chose the top 50 using the 3-hour ACM format (problems in Russian, results, top 5 on the left, discussion in Russian). rng_58 quite succesfully continued working towards his goal of learning Russian by claiming third place in a contest with Russian problem statements only, although most probably translation software has played a part.

The hardest problem was probably the most beautiful, too. You are given a row of n devices, each consuming some subset of 8 different resources when turned on, and producing some amount of energy when turned on. For each l from 1 to n you need to find the smallest r such that it's possible to turn on some devices from the segment [l;r] such that no two devices turned on consume the same resource, and that the total energy of the devices turned on it at least z. Solving this problem for each particular value of l is a relatively straightforward dynamic programming question, but given that n is up to 100000, we can't affort to solve each l separately.

And finally, Google Distributed Code Jam 2015 Online Round brought an entirely new competition format to the best competitors in the world (problems, results, top 5 on the left, discussion). Of course, it might turn out that the best competitors for this new format will be completely different ones - that's why it's so exciting to see how it pans out.

So far, it looks like the competition went well, and there are only two competitors who have qualified both for the regular and for distributed Code Jam: simonlindholm and bmerry, definitely suggesting that the distributed part tests quite different skills. People who participated: do you share this feeling? Was solving these problems similar to more usual contests?

Thanks for reading, and see you next week!