← All solutions

Solved by 41 teams.

First solved after 44 minutes.

Shortest team solution: 988 bytes.

Shortest judge solution: 590 bytes.

This problem was not as hard as the teams made it out to be, but the presence of a geometry component made it look a bit scary. There is a simple but too slow O(n3 )-time solution using quite standard dynamic programming: find the cost to cover the first i points of the ground profile (with a pillar on the ith point), by considering all positions j < i for the second-last pillar. One must then check that ground profile between j and i does not intersect the arch.

We improve this with some precomputation. Suppose there is a pillar at point i, and consider expanding the arch to the right of it. The left half of the arch will require increasingly more space, until it cannot grow further without intersecting the ground. Similarly, we can determine an upper bound for the size of the arch to the left of i for the right half of that arch not to hit the ground. By combining this information, we can determine in O(1) whether any given arch is valid, allowing the dynamic programming to be performed in O(n2 ).