Flint and Steel

Turn explosions into intervals

For a creeper $i$ with $e_i>0$, detonating it kills

$$L_i = \max(1, i-e_i+1),\qquad R_i=\min(n, i+e_i-1).$$

Creepers with $e_i=0$ are never usable as detonations.

If this were just “cover $[1,n]$ with the fewest intervals”, life would be easy. But there is one annoying rule: a creeper must still be alive when we detonate it. So if we choose two creepers that can kill each other, whichever one we detonate first deletes the other one. That pair cannot both be used. Very rude, very Codeforces.

What a valid chosen set looks like

Take the chosen creepers and sort them by position:

$$p_1 < p_2 < \dots < p_k.$$

We can assume every chosen interval extends the covered prefix. If a chosen creeper does not extend the farthest killed position to the right, removing it still covers all positions and cannot make the sequence less valid. So in an optimal solution, the prefix endpoints strictly increase.

Now consider two consecutive chosen creepers $j<i$ in this position order. To cover without a gap, we need

$$R_j \ge L_i-1.$$

Also, the new interval must extend farther:

$$R_j < R_i.$$

The pair is valid if they do not kill each other. Since $j<i$, there are two safe cases:

1. $j$ does not kill $i$: $R_j < i$.
2. $i$ does not kill $j$: $j < L_i$.

At least one of these must hold, otherwise both centers lie inside each other's blast radius, and using both is impossible.

The DP state

Use a segment tree over prefix endpoints $0,1,\dots,n$.

At position $x$, store the best pair

$$(\text{number of detonations},\ \text{last chosen creeper})$$

among ways to kill exactly the prefix $1\ldots x$ using only creepers processed so far.

Base state:

$$\text{seg}[0]=(0,0),$$

meaning we have killed nothing and chosen no last creeper.

For each usable creeper $i$, we want the best predecessor chain that can come before it.

Let

$$a=L_i-1=\max(0,i-e_i),\qquad b=R_i.$$

There are two transition types.

Case 1: previous blast stops before $i$

We need

$$R_j \in [L_i-1, i-1].$$

This query should be made after all possible previous centers $j<i$ have been processed. So we schedule it at time $i-1$:

$$\min \text{seg}[L_i-1 \ldots i-1].$$

Case 2: previous center is left of $i$'s blast

We need $j<L_i$. Instead of storing $j$ in the query, we enforce this by timing: make this query right after processing center $L_i-1$. Then the segment tree contains only chains whose last center is at most $L_i-1$.

The previous endpoint must connect to $i$'s interval and must be before $R_i$:

$$R_j \in [L_i-1, R_i-1].$$

So we schedule

$$\min \text{seg}[L_i-1 \ldots R_i-1]$$

at time $L_i-1$.

The minimum of these scheduled query answers is $dp[i]$, the best number of detonations before adding creeper $i$. Then selecting $i$ gives $dp[i]+1$ detonations and covers prefix $R_i$, so we update

$$\text{seg}[R_i] \leftarrow \min(\text{seg}[R_i], dp[i]+1).$$

We also store the predecessor creeper from the segment tree answer, so reconstruction is just following parent pointers.

Why this does not miss weird non-adjacent conflicts

The DP explicitly prevents consecutive chosen creepers from killing each other mutually.

Could a non-consecutive pair still mutually kill each other? Suppose earlier chosen creeper $h$ and later chosen creeper $i$ mutually kill each other. Let $j$ be the immediate predecessor of $i$ in position order. Since endpoints strictly increase, $R_j>R_h$. Because $h$ kills $i$, we have $R_h\ge i$, so $R_j\ge i$ too, meaning $j$ also kills $i$.

And since $i$ kills $h$, and $h<j<i$, $i$ also kills $j$.

So $j$ and $i$ would be a mutually killing consecutive pair, contradiction. Nice little trapdoor proof.

Getting a valid detonation order

After reconstructing the chosen creepers, sort them by increasing explosive power $e_i$.

Why does that work? If an earlier printed creeper $a$ killed a later printed creeper $b$, then

$$|a-b| < e_a.$$

But because we sorted by power, $e_a\le e_b$, so also

$$|a-b| < e_b,$$

meaning $b$ kills $a$ too. That would be a mutual-kill pair, which we already proved cannot exist. Therefore every printed creeper is alive when detonated.

Complexity

Each creeper creates two range-min queries and at most one point update. Everything is segment tree work, so the complexity is

$$O(n\log n)$$

per test case, with $O(n)$ memory.