Flint and Steel

Problem

Hint

Consider the following subproblem: given an unordered subset of creepers, can we find an order of detonation such that no creeper is killed before it is detonated?

Solution

A simple case where no such order exists is when the detonation intervals of two creepers both contain each other, like so:

This turns out to be the only case where no viable detonation order exists. Moreover, it turns out that we can always just determine the detonation order by detonating the creepers in order of increasing radius.

We can show this with a proof by contradiction. Assume that the smallest detonation interval, which belongs to creeper $x$, contains another creeper, $y$. Then, according to our condition above, the detonation interval of creeper $y$ cannot contain creeper $x$. However, this means that the detonation radius of creeper $y$ must be less than creeper $x$‘s: a contradiction.

The bottom-most interval represents creeper $x$, and the red ones represents possibilities for creeper $y$. Both are impossible because they either contradict our assumption that $x$ has the minimum radius, or the condition that no two creepers contain each other’s centers.

Now, the problem reduces to finding an unordered subset of minimal size that satisfies the following requirements:

• Together, the chosen detonation intervals must kill all creepers.
• No two detonation intervals can contain each others’ centers.

This is easily done with dp + segment-tree in $\mathcal{O}(n\log n)$.

Implementation