I only read through the problems once and didn’t spend too much time thinking about them, but here’s my analysis based on my first impression. First, check out the problem set here.
A. This problem looks reasonably straightforward. Most teams solved it. There’s only 8 planes, so you can try all 8! orderings and use binary search to compute the minimum time. After that, place all planes as close together as possible and keep track of the best answer.
B. I don’t think there’s anything particularly tricky about this problem. I believe you just implement the gates and simulate the execution. In the situation where you need to track down the bad gate, you can try making each gate bad and see which one results in correct answers. There’s only 19 gates, so it should be pretty do-able.
C. This problem is very similar to a classic problem with an ant or spider on a cube. I actually received this problem during a job interview once. With the cube, you unfold the cube in every possible way and then compute the shortest distance in 2D. For an octahedron, the same process should work. It’s probably a bit tricky to get all the details correct.
D. Only idea I have is to try all possible configurations.
E. Haven’t solved it yet.
F. Doesn’t look too bad and a lot of teams solved it. I think you can compute the convex hull between points and then extend that based on the margin. You can combine this perimeter with rounded segments based on circles enclosing the points. To figure out the smallest fence, use dynamic programming (DP) over the point subsets and fence lengths.
G. This is a two player game problem, but I think you can bruteforce it. You have to carefully implement the various rules of the game, but the number of possible states is reasonably small provided you cut branches that are bad.
H. This problem can be formulated as 2-SAT, which has a well-known solution using depth-first-search. To determine the result for a variable, you can fix the answer and run 2-SAT, checking if the formula is still satisified.
I. I need to read this problem again, but it looks like a simulation problem.
J. Not sure of the details yet. Looks like DP.
K. Looks like DP mixed with shortest-path. Haven’t worked out the details.
Looks like a good set of problems. There was a decent spread of the teams, with most solving at least one or two, and no team solving them all.
