Sunday, October 10, 2021

A 2020 week

ICPC 2019-20 World Finals was the first event of this week (problems, results, top 12 on the left, official broadcast, our stream). As this is the main event of the year for many competitors, there are quite a few reports to check out from various participants (1, 2, 3, 4, please post more links in comments!). I did not watch the contest myself as we were solving it on stream instead, so let me just congratulate all medalists, and especially the NNSU team on the victory!

It was amazing to meet so many old and new friends in person after the long break, so big thanks to the organizers on making this event possible! At the same time, I think that the 3-computer rule and the fact that it was only announced a few weeks before the event were quite unfortunate. I hope that we will return to the 1-computer format next year!

On the heels of the World Finals where JetBrains was one of the main sponsors, Codeforces hosted Kotlin Heroes Episode 8 (problems, results, top 5 on the left, analysis). Judging by the standings, there was a nice difficulty curve that allowed everyone to have something interesting to solve. 3 contestants were able to solve one of the two hardest problems, SpyCheese finishing ahead of Heltion and eatmore thanks to being much faster on the relatively easier first 8. Congratulations!

TopCoder SRM 815 took place on Friday (problems, results, top 5 on the left). I was solving the round with a cold and a headache, however somehow this did not affect the results much, maybe because the 250 and 500 were very standard, which allowed me to go through them more or less on autopilot.

Solving the hard problem, on the other hand, required some gut feeling for what will be fast in practice. Given two positive integers n<=50 and m such that mn<=1018, what is the largest possible value of the least common multiple of n positive integers, each up to m?

Facebook Hacker Cup 2021 Round 3 wrapped up the week on Saturday (problems, results, top 5 on the left, analysis). The combination of point values with the ICPC penalty time system created an interesting strategic dilemma: solving tasks D2+D3 (which was not really much more difficult than solving one of them) required more time than solving problem B or problem C, but since they were counted as two for penalty time purposes, it could pay off in terms of penalty time. From the top two finishers, tourist went for D2+D3 first, and Radewoosh went for B+C first, and the strategies turned out to be really close in practice. Well done to both, and congratulations to the top 25 who will compete in the online finals!

Going with D2+D3 before problem C had another drawback: in case one did not have enough time to solve everything, since D2+D3 were worth less points than C, one would lose to the alternative approach. The set of people on 68 points in the scoreboard has quite a few favorites who ended up not qualifying despite solving the most difficult problem. So in effect one had to decide between a strategy that would deliver the smallest penalty time when solving everything, and a strategy that would give more points when solving all problems except one (if we treat D2+D3 as one problem, as they really were).

I would also like to bring two important competitive programming websites to your attention. clist.by has the information about virtually all competitive programming contests, and allows everyone to assemble a custom calendar with regexp-based filters to see only the contests one is interested in. It also has Telegram notifications for this customized calendar and also imports the standings from most of those contests which allows for contestant-vs-contestant comparisons across platforms. It obtains the links between handles on different platforms through crowdsourcing, you can link all your handles together after registering on clist.by.

The recently launched cphof.org is similar in spirit, as it tries to create a unified profile for the contestants through various platforms and one-off competitions. However, it focuses only on big tournaments and not on regular rounds, and this limited scope allowed it to do the linking without relying on crowdsourcing. As a result, it has really good coverage for the top competitors.

Huge thanks to the maintainers of those websites, I use them every week! And thanks to all for reading, please check back next week.

Monday, October 4, 2021

An invitational week

TopCoder SRM 814 was the first round of last week (problems, results, top 5 on the left). ecnerwal was about 5 minutes faster than the rest of the field in solving the 1000-pointer, and therefore got enough margin to maintain the first place through the challenge phase and deny me qualification to Round 4 of TCO22 :) Well done!

Codeforces Round 745 followed later on the same day (problems, results, top 5 on the left, analysis). The last two problems were a lot harder than the rest, and only medium_waxberry and maroonrk were able to crack them. Congratulations to both!

ACM ICPC 2019-20 World Finals finally takes place tomorrow in Moscow. In case you haven't been following, quite a few teams could not make it and participated in a different online contest instead, and for those who could, the format was changed to 3 computers instead of 1. From the teams that made it to Moscow (list, but you have to exclude the online teams), the strongest three are the MIT, the Nizhny Novgorod SU and the Seoul NU. It seems that the battle tomorrow will be quite exciting!

I hope there will be an online mirror, and we'll solve it together with Gennady Korotkevich and Mikhail Tikhomirov for the fourth time in a row (2017, 2018, 2019), streaming the process online. We will use only 1 computer and stream to Gennady's Twitch channel this time. Tune in tomorrow around 9:15am Moscow time and ask your questions in chat! There is also an amazing official stream with commentary.