Tuesday, December 29, 2020

A rng_58 week

Last week wrapped up the year for two major contest platforms — TopCoder and AtCoder — and with it the races to qualify to the corresponding onsites.

TopCoder SRM 796 was the first round of the week (problems, results, top 5 on the left, analysis). maroon_kuri was leading after the coding phase but failed the system tests; none of myself, tourist and Egor could find a challenge opportunity even though there were lots of them available, including in the 500-pointer which screamed "look for challenges here!" as it had just one sample case.

This round concluded the three-month race for the second TCO21 spot (results, top 5 on the left). Even though six SRMs is quite a lot, the race came down to the wire and to a lot of very close calls: in SRM 792, neal_wu produced an amazing 200-point challenge phase to get a 3-point advantage and deny Um_nik the 5 race points; in SRM 793, tourist's easy was challenged but he would still win the round had ksun48 not taken his turn to earn 200 challenge points; you can see the story of SRM 796 above.

AtCoder held its two last rounds of the year on the weekend, starting with AtCoder Grand Contest 050 on Saturday (problems, results, top 5 on the left, analysis). Um_nik was the fastest on the four relatively easier problems, and protected his lead by finding the main insight and figuring out all details in the very tricky problem F. Congratulations on the win! duality and newbiedmy were also able to solve the hardest problem, and rounded up the top three. newbiedmy in particular must've had one hell of a contest: he started with this problem, and did not give up after 11 incorrect attempts. This unusual strategy was richly rewarded!

AtCoder Grand Contest 051 on Sunday was the last contest of rng_58 as AtCoder admin (problems, results, top 5 on the left, analysis). Even though the point values were different, the scoreboard looks very similar: the first four problems were solved by many, while the last two were very hard and only got accepted solutions in the last 45 minutes of the 4.5-hour contest. semiexp and yutaka1999 went for problem F which gave them more points and the first two places. Congratulations!

I'd like to highlight problem D: you are given an undirected graph with four vertices and four edges that looks like a square (the picture from the statement on the right). You know that a walk started from vertex S, finished at vertex S, has passed the ST edge (in any direction) a times, the TU edge b times, the VU edge c times, and the SV edge d times. How many different walks fit that description? a, b, c and d are up to 500000, and you need to compute the answer modulo 998244353.

Given that Makoto (rng_58) is retiring as AtCoder admin, I'd like to thank him for bringing AtCoder to the English-speaking world, and for making it the place for solving awesome problems. Extremely well done!

The two rounds have concluded the race for the 8 AtCoder World Tour Finals spots (results, top 8 on the left). Congratulations to all finalists! This is the third season of the AtCoder points system. The top 8 has quite a big intersection with those from the two previous years (2018, 2019), with tourist, Um_nik and myself qualifying all three times, and ecnerwala and mnbvmar qualifying last year. It will be the first WTF for Benq, Stonefeang and endagorion, assuming it does actually take place of course :)

Thanks for reading, and Happy New Year!