← All solutions

Solved by 2 teams.

First solved after 270 minutes.

Shortest judge solution: 4442 bytes.

Consider a lava moat at height h, which does not pass through any vertex. The moat can be shifted to a slightly different height h + e, and the path (and its length) will vary linearly with e. Thus, we can either improve the length by choosing a small positive or negative e, or the length will stay the same until we choose a sufficiently large e that the path hits a vertex. So we can assume the optimal path passes through a vertex.

Suppose we already knew the optimal height h, corresponding to a map vertex V. We could then consider every triangle and find the segment that crosses it at height h (if any). These segments form a graph, with the map edges as nodes (as well as V, but we will temporarily ignore that). Each map edge forms part of at most two triangles, so graph nodes have degree at most two, and thus the components are linear chains (terminating at the map borders or at V) and cycles. The shortest path could be found by looking at the chains terminating at V and taking the shortest one that terminates at the west border and the shortest one that terminates at the east border.

Building the whole graph for each possible V is too slow (quadratic time). Instead, we can sweep through the possible values of h from lowest to highest, and keep updating the graph as edges appear and disappear. One approach is to use an offline dynamic connectivity algorithm: edges have associated lifetimes (specified in ranges of h values) and are added to a segment tree, and we then do a traversal of the segment tree using a disjoint set union data structure that supports unwinding when moving back up the tree. For each connected component, we need to keep track of the total length (as a linear function of h) and which borders it touches. This works because the components that touch a border are simply linear chains, and hence the total length is also the shortest path length.

The total runtime is O(n log² n). There are other possible solutions that use more complex data structures to do online addition and removal of edges, and which run in O(n log n).