A 2015 week

TopCoder Open 2018 onsite event in Dallas was headlining the Nov 12 - Nov 18 week. The first semifinal took place earlier on Thursday (problems, results on the left, broadcast, analysis). tourist ended up dominating the proceedings by solving the 1000-pointer in just 15 minutes, but of course the main goal in this round was getting into the top 4. There was quite some drama involved as Egor ended up fifth after resubmitting his solution for the 250-pointer because the original solution could not handle exactly one case correctly: 1x1 grid. Congratulations to tourist, Errichto, Um_nik and ACRush on advancing to the final!

The medium problem in this round was a great combination of simple statement and exciting problem solving, while still being medium difficulty: you are given an integer n up to 10¹⁸. You need to return any 4-connected figure which has exactly n different domino tilings, and which fits into a relatively small bounding box: the area of the bounding box must not exceed 14400, and the height of the bounding box must not exceed 13 (I guess this second condition was required to make it possible to check the output for correctness in reasonable time). Can you see a way?

Semifinal 2 followed very late on Thursday (problems, results on the left, broadcast, my screencast, analysis). Before the semifinal rounds I was telling other contestants that I expect that a fast 250 should be mostly enough to get to 4 out of 8, as you can expect some people to fail the system tests and ending up above them is enough with such generous advancement rules. Well, apparently I had to support my theory by example this time :) You can see from the screencast that I knew that my medium solution was incorrect, but I could not fix it (it turned out that the approach is probably impossible to get to work), and there was just too much implementation involved in the hard problem. During the challenge phase I was very happy when my medium was challenged because the challenger was not Kankuro, and thus I was still solidly in top 4.

The final round took place one day later, on Friday (problems, results on the left, broadcast, my screencast, analysis). There were a couple of important decisions that shaped this round for me.

First, I've decided to implement a quite tedious solution for the easy problem (which was actually incorrect but not caught by system tests). That led to the situation where after submitting the easy I was quite a bit behind, and seeing as the leader tourist has opened the medium problem after solving easy, it felt that going for the hard would increase my chances for the first place.

Then I was actually able to solve the hard problem quite quickly thanks to coming up almost immediately with the key solution idea: that diagonals can be handled independently. This might've been helped by the fact that I have seen this idea before, and in a very similar setting: my previous TopCoder Open victory in 2015 had medium problem with the reference solution using exactly this idea (I did not come up with this idea in 2015, so you can't say that one idea got me two wins, but still the parallels are amusing).

Then I've tried to solve the medium problem, had some good ideas but could not make the solution work, and had almost given up — but then Kevin has submitted his medium with about 9 minutes to go and overtook me in the standings. This was apparently just the extra bit of motivation I needed, as I've then resumed my attempts at solving the medium and managed to submit it with just about 50 seconds remaining in the coding phase! Once again some remarkable parallels to the situation three years ago :)

Here's the medium problem that caused all this excitement: you are given n<=200 points on the plane. You need to connect some pairs of points with straight line edges, so that you build exactly n-1 edge and the result forms a tree. What is the minimum possible diameter of the resulting tree (the maximum distance between its vertices, were the length of each edge is equal to the corresponding Euclidean distance)?

After the dust from the TCO finals had settled a bit, Open Cup Grand Prix of Siberia took place on Sunday (results, top 5 on the left). Both the team Past Glory and the ICPC world champion team from Moscow SU were able to solve 11 problems, but with 13 penalty attempts against 3 and corresponding debugging time the Moscow team had almost 50% higher penalty time. Congratulations to the team Past Glory on the victory!