A unit week

The Jul 30 - Aug 5 competitive week started early with Codeforces Round 500 on Monday (problems, results, top 5 on the left, analysis). There were a few strategy options on the table, as the last two problems had the same point value and some people went for E and some for F: E turned out to be the right choice. Congratulations to Um_nik on the win!

Facebook Hacker Cup 2018 Round 2 followed on Saturday (problems, results, top 5 on the left, analysis, my screencast). Getting into the top 200 was the main goal, but there was some competition for the top spots as well, where Alex was a bit faster than everybody else. Well done!

In my previous summary, you are given a program for a drawing robot consisting of at most 250000 commands. Each command is either F "move forward by 1 unit, drawing a line", L "turn left by 90 degrees", or R "turn right by 90 degrees". The drawn polyline splits the plane into multiple regions, some finite, some infinite. Your goal is to return the list of the areas of all finite regions.

There's a somewhat well-known approach to the general problem of finding faces of a planar graph which is described in the official analysis. However, I've used the specifics of the problem and went with a different approach that I found less bug-prone.

Let's imagine the plane as a grid, split the polyline into unit segments, and look at the vertical unit segments for now. Every row of the plane will be split into two infinite blocks plus some finite k times 1 blocks by the vertical unit segments. The overall number of finite blocks is at most 250000.

Now let's put those blocks into a disjoint-set data structure, and merge the blocks that are adjacent vertically. In order to find the latter, we need to iterate over pairs of adjacent rows with two pointers, and not forget to take the horizontal polyline unit segments between those rows into account.

While the general planar graph algorithm is not harder than this one, I found that this approach allows to sidestep all corner cases, for example: what if there is a vertex of degree 1? What if there's more than one connected component of the polyline (not possible in this problem)?

Thanks for reading, and check back for more!