Sunday, November 15, 2020

A clean slate week

I think it's really past time to admit that I can't keep up with the weekly schedule, and start enjoying writing the posts instead of stressing about the backlog of several months. So, here comes:  

This week's competitive programming events started with the Kotlin Heroes 5 on Codeforces (problems, results, top 5 on the left, analysis). Gone is the idea to auto-convert from Java, as everyone in top 5 seemingly writes somewhat idiomatic Kotlin directly (however I'm wondering if it looks idiomatic to Roman Elizarov :)). tourist and Benq were the only contestants to solve all problems, but Benq's chance to catch tourist was mostly gone with the incorrect attempt on problem D on the 12-th minute, which he took 9 minutes to correct and therefore fell behind so much he could not really recover. Congratulations to both on the great performance!

TopCoder Open 2020 has opened its virtual doors with Semifinal 1 (problems, results on the left, stream recording). The round was marred by an incorrect reference solution for the 500, seemingly making the problem unsolvable, at least within the time of the round, and resulting in neal_wu's challenge requests not being processed. In the end, the organizers have awarded him 50 challenge points as well (so we got +100 challenge points with just one incorrect submission :)), and advanced five competitors to the finals instead of four. Congratulations to all five! I think this is a decent solution to this situation, but I'm wondering if rerunning the round from scratch with a different set of problems would (arguably, of course) be more fair.

I have been commentating the round on the stream, and I didn't really do it well. First of all, I've had one job — to read the handles of the Russian competitors correctly — and still managed to mispronounce Um_nik's handle :( To add insult to injury, I did not name him in my list of contestants who have been doing very well recently, which was of course an obvious oversight. I'd like to take this opportunity and apologize to Alexey!

There were also serious connection issues which resulted in my voice not making it to the stream in many cases, and in us talking over each other a few times :( In addition, I have assumed that the first solution for the medium that came to our mind would run in time, while it actually did not. Streaming is hard! Please share any improvement suggestions that you have, I hope to do better next time.

AtCoder Grand Contest 049 followed on Saturday (problems, results, top 5 on the left, analysis). Um_nik breezed through the first five problems, and since the last problem was too tough to crack, his first place was not really in doubt. Well done! The race towards the 8 WTF spots is close to its conclusion (assuming there will be 1 or 2 more qualifying AGCs), with the top 4 most likely already booking their spots, mnbvmar being almost there, and maybe maroonrk as well if he keeps being a writer in the remaining rounds :)

In keeping with the meta-story of problem E, I came up with a solution that seems to have exactly zero things in common with the editorial :) Here is the problem statement: you start with a sequence of n zeros (n<=50), and can apply the following four operations any number of times:
  1. Add one to any number. This operation costs 1.
  2. Subtract one from any number. This operation costs 1.
  3. Add one to any contiguous segment of numbers. This operation costs C.
  4. Subtract one from any contiguous segment of numbers. This operation costs C.
Now, you are given k (k<=50) candidates for each value in the final state of the sequence, each candidate is between 1 and 109. You need to find sum of the minimum costs to obtain the final state for each of kn possible final states, modulo 109+7.

Right after the end of the AtCoder round, Errichto hosted the final 8 of the first open Lockout tournament organized by Geothermal (detailsstream recording, top 8 bracket on the left). pseudocoder10 has created an excellent bot that runs the matches and automatically picks Codeforces problems of appropriate difficulty that both participants have not solved yet, and the system with 6 problems and 100-200-300-400-500-600 point values provided for a big strategic variety and made the matches very exciting to watch. Well done to everyone involved, and congratulations to Um_nik on the victory!

rng_58 is running another iteration on new problems (future AtCoder Regular Contests), consider signing up if you're 2800+ on AtCoder!

Codeforces Round 683 wrapped up the week (problems, results, top 5 on the left, analysis). Um_nik has solved problem E in a seemingly normal rhythm, and went on to solve everything with almost half an hour to spare and win the round. Most of the others could not get past pretest 3 in problem E (Um_nik also had two attempts that stopped there), with ksun48 advancing as far as pretest 5. Congratulations to Um_nik on the convincing victory!

The diff between his passing solution and "wrong answer on pretest 3" attempt is small, but it does seem to be a substantial fix to the solution logic (see it on the right).

Thanks for reading, and check back (maybe) next week!


  1. Yes this is entertaining. Reading backlog posts was never fun :P

    Stream suggestion: don't worry too much about it. As long as the internet connection is fast, which is essential, I quite enjoyed your comments on the round. You were speaking too less! Speak more HAHAHA

  2. Hi! I was among the authors team of CF#683. We thought E wasn't that hard (I wonder what's Um_nik's opinion on this), the solution is fairly easy to implement and consists only of quite natural observations. Most of the contestants preferred more standard problem F to spend their time on.

    Happy to see you gave up on the backlog to write about recent events :)

    1. E wasn't that hard, but for sure it's by far the hardest problem from the round. F is just obvious binary search + (you don't need any data structure in USACO problem, but the main idea about tangents is the hardest part, after that it's just technical). I'm actually pretty surprised that the number of AC in contest is not in the 50s: the tangents idea should be quite well known by now and everything else is pretty easy. From my perspective D2 is harder than F, but that might be just me being stupid at D2.

  3. 100 years from now, some CP historians will be angry at you for breaking the continuity.

  4. About TCO stream: It's quite hard to switch to Russian when everyone speaks English and you did pronounce my handle as English-speakers do so nothing criminal here :) It was funny, but not offensive in any way. Also I'm not doing well on TopCoder so again: not a mistake.

    About fix in CF problem: It was not actually a very substantial fix to logic. I managed to make two mistakes in handling the corner case (although it really is quite tricky and is a big part of solution so I'm not sure I can dismiss it as "just a corner case"), but idea-wise the solution was correct when I had started to code it. Both bugs were caught with small handcrafted tests.