A center week

The Nov 19 - Nov 25 week had its contests on Sunday, the first one being Open Cup 2018-19 Grand Prix of Dolgoprudny (results, top 5 on the left). For the third time in the last four Open Cup rounds, the team Past Glory was first and the team Moscow SU: Red Santa was second, with quite a huge gap stemming from the large amount of incorrect attempts for the Red Santa. Congratulations to both teams on yet another strong performance!

Codeforces hosted Mail.Ru Cup 2018 Round 3 later that day (problems, results, top 5 on the left, overall results, analysis). Radewoosh continued his fine recent form, solving all problems with 15 minutes to spare and with just two incorrect attempts, compared to V--o_o--V's nine. Congratulations on the win!

In my previous summary, I have mentioned two TCO onsite problems. The first one was constructive: 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.

It's very easy to build multiplication: given two figures with a and b tilings respectively we can build a figure with a*b tilings by concatenating them possibly with a small insertion in the middle so that no new spurious tilings appear.

However, in order to build arbitrary numbers we usually need both multiplication and addition, and addition is where the main difficulty lies: since the number of domino tilings is a "global" object, it's not clear how we could achieve "either a or b" behavior.

The official analysis shows two great ways to achieve addition, based on the idea that we can build figures that have only one tiling with one "parity" and lots of tilings with other "parity". Please look there for more details (the problem name is "DominoTiling").

The second problem I mentioned was of the more traditional optimization style: 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)?

Solving this problem required a good understanding of how distances in trees work. More specifically, if we take any diameter of a tree, and find its middle point (which might be a vertex and might be in the middle of an edge), this point will be the center of the tree: all vertices of the tree will be at a distance of at most d/2 from it (where d is the diameter). Moreover, the opposite is also true: if there's a point in the tree such that all vertices are at a distance of at most d/2 from it, then the diameter of the tree is at most d. The important aspect here is that we don't have to consider the distances between pairs of vertices anymore — all that matters are the distances to the center.

Suppose the center lies in the middle of the edge connecting vertices u and v. Then for the part of the tree containing u the distances to the center are going through u. Then we can notice that because Euclidean distance satisfies the triangle inequality, if we rearrange that part of the tree to have all other vertices connected directly to u, the distances to the center will not increase, which means that the diameter will not increase, too.

In other words, we can assume that the optimal tree always looks like an edge u-v, and all other vertices are connected to either u or v.

Moreover, we can see from the above argument that all that matters in the optimal tree is the maximum distance from u to a vertex connected to it, and the maximum distance from v to a vertex connected to it, and thus when deciding whether to connect each other vertex to u or v we just need to think about those two numbers. For example, suppose that w is the vertex farthest from u that is connected to u. Then we can connect to u all vertices that are closer to u than w without increasing the diameter, so the set of vertices connected to u will be a prefix of all vertices sorted by distance to u (during the contest I've sorted by the difference of distances to u and v, which also works).

This allows an O(n³) solution: try all possibilities for u and v, all prefixes of the list vertices sorted by distance to u. Connect the vertices from the prefix to u and the rest to v, and find the minimum diameter of all trees built in this way.

Note that we still need to find the diameters of those trees properly, as we're not guaranteed that the center will be on the u-v edge for any such tree, and finding the diameter properly requires finding the maximum and second maximum edge connected to each of u and v, which can be done by computing prefix and suffix maximums and second maximums.

The "second maximum" part can be avoided if we remember that we don't really care about the cases where the center is on the u-v edge — we just need to make sure that those cases don't incorrectly get a too small diameter computed. For example, Kevin does in fact check in his solution if the diameter is on the u-v edge and throws away the tree if it's not; however, since the distances are floating-point we might get rounding issues here if the optimal center is in fact a vertex, so he had to handle that by adding an epsilon to the comparison. Gennady, on the other hand, just computes the diameter in pessimistic fashion for such trees: if the center ends up being outside the u-v edge, we compute the diameter as 2 times the maximum distance from u and v to other vertices. This will never be less than the actual diameter, and for the cases where the center is u or v this will be equal to it, just as we need.

Thanks for reading, and check back for more!