A Gennady week

Last week saw the first elimination round of Google Code Jam 2020, Round 1A (problems, results, top 5 on the left). Gennady.Korotkevich started his title defense with another commanding performance in the middle of the night, wrapping up 10 minutes before everybody else. Well done!

TopCoder SRM 783 followed later on Saturday (problems, results, top 5 on the left, my screencast, analysis). tourist, bqi343 and scott_wu were much faster than other top competitors on the 1000, but Scott's 250 failed to handle perfect squares correctly, and Ben's single challenge was still not enough to catch Gennady. Congratulations on the second victory of the day!

The hard problem had two almost independent parts: solving the k=1 case, and understanding how to reduce k>1 to k=1. The problem statement was: you are given a directed tournament with n<=23 vertices. You are then constructing a "power" of this tournament with n^k vertices (k<=1000), with each vertex described with a k-tuple of vertices of the original tournament. The direction of the edge between two k-tuples is given by the direction of the edge between the vertices that appear in the first position the k-tuples differ. For example, the direction of the edge between (a, b, a, c) and (a, b, d, e) is the same as the direction of the edge between a and d in the original tournament. How many subsets of vertices of this big graph induce a strongly connected subgraph, modulo 998244353?

The k=1 part — where the graph with at most 23 vertices is just given to you directly — allowed quite a lot of interesting and different solutions, so I encourage you to try solving at least that part :) I believe my solution did not in fact need the graph to be a tournament, it could handle any directed graph, so you can try solving either version.

This was the first time I was recording a screencast while using an external 4K monitor, which brought a couple of challenges: first, it seems that encoding a 4K video was using nearly all resources of my machine, even though I was using the same bitrate as I did for the 1080p video. This meant I had to wait for half a minute every time I ran my solutions, somewhat suboptimal :) Second, the fonts in the arena looked really funny, most likely because I had font scaling enabled in Windows to be able to read text in such resolution. Any suggestions on how to resolve those?

Codeforces Round 633 took place on Sunday (problems, results, top 5 on the left, analysis). My approach turned out to be very similar to previous week's Codeforces round, solving four problems at reasonable speed but then giving up too easily on the fifth, instead looking for challenges when there were virtually none available — the only failing solution in my room was hos.lyric's D, and I did not really suspect it to be incorrect. tourist was in a similar spot in the middle of the leading pack after solving four problems, but went on to win the round after solving E. Congratulations on three wins in a row!

Radewoosh jumped into the second place with a correct submission on E with 7 minutes remaining, then almost blew it by actually submitting a version without bitsets, and then some version with bitsets but also with too much debug enabled, and finally submitting the correct bitset solution again with just seconds remaining in the round. What was that? :)

Problem D was quite nice: you are given a tree with n<=10⁵ vertices. You want to draw n closed curves on the plane, one per vertex, in such a way that two curves intersect if and only if the corresponding vertices are adjacent in the tree. What is the maximum size of a chain of curves that are nested in one another (but do not intersect) in such drawing?

Thanks for reading, and check back next week!