An obtuse week

The Jun 4 - Jun 10 week was the week of the Google Code Jam: the onsite advancers were determined both in the normal and in the distributed competition.

First off, the Google Code Jam 2018 Round 3 took place on Saturday (problems, results, top 5 on the left, analysis). Somewhat surprisingly, none of the full scores stood during the system testing. Errichto.rekt and ifsmirnov lost the least points at that stage :) Congratulations!

I found the problem Name-Preserving Network really exciting. You are given a number n between 10 and 50, and need to print a connected simple undirected graph with n vertices, and each vertex having degree exactly 4. The interactor will then randomly permute the vertices of your graph and give it back to you, and you need to then restore the permutation that was used. In other words, you need to find such graph without automorphisms, and be able to identify its vertices after they're shuffled. How would you approach this one?

The Distributed Code Jam 2018 Online Round followed a day later (problems, results, top 5 on the left, analysis). Errichto.rekt was at the top for the second day in a row, thanks to being one of only two solvers of the hardest problem E. Well done!

In my previous summary, I have mentioned an unusual TopCoder problem: You are given 3n sticks with lengths a, a+1, ..., a+3n-1. You need to find any way to split them into n triples in such a way that each triple forms a non-degenerate obtuse triangle, or report that there isn't one. n is up to 500, a is an integer between 1 and 10.

There are a few principal approaches to this kind of problem (did I already enumerate those on the blog? Please share a link, and also please add ones that I missed):

• Just solve the problem on paper, in other words come up with a direct explicit construction.
• Solve the problem on paper in two steps a-la induction: come up with a way to solve the problem for small instances of the problem, and also come up with a way to change a solution for n to a solution for n+5 (for some value of 5).
• Only do the second inductive part on paper, and use brute force to find solutions to small instances.
• Also replace the inductive part with something less formal: do some kind of greedy for most of the solution, and use brute force when the remaining problem is small enough.

The official analysis suggests to use the third approach, while I went with the last one since it requires the least amount of thinking :)

I like to code such solutions as a brute force that runs even for large values of n, with the greedy part being implicit by the order the brute force tries the possibilities: since for most of the decisions, we will never have time to come back to them, the first decision we try in the brute force is effectively the greedy decision. This way I don't have to explicitly choose the boundary between the greedy and the brute force, and thus can try different ideas faster.

You can take a look at my solution from the round for more details, but in short, the ordering that worked was: as the first attempt, try to pair the smallest remaining stick with the 1/3-rd and 2/3-rd ones in sorted order, and then go from those in both directions.

Thanks for reading, and check back for more!