Lizards and Basements 2

Observation 1: the order is fake complexity

Let $x_i$ be how many times we shoot archer $i$ for $i$ from $2$ to $n-1$.

Because damage is additive and the statement explicitly allows shooting dead archers, only the counts $x_i$ matter. The sequence order does not. For an internal archer $j$ the total damage is

$damage_j = b x_{j-1} + a x_j + b x_{j+1}.$

For the edges, only one neighbor term exists.

We need every archer to end with health <0, not <=0. Yes, the game is that petty.

A brute force over all vectors $(x_2, ..., x_{n-1})$ is still ugly: each $x_i$ can be up to $16$, so this is about $17^{n-2}$. Too much.

Observation 2: only two archers matter at a time

Suppose we are about to decide how many times to shoot position $i$.

All shots on positions $2$ to $i-1$ are already fixed.

Now look at who can still change:

• Archers $1$ to $i-2$ can never be hit again, so they must already be dead.
• Archer $i-1$ can still be hit only by shots at $i$.
• Archer $i$ can still be hit by shots at $i$ and $i+1$.
• Archer $i+1$ is untouched so far, because the leftmost spell that can hit it is exactly position $i$.

So the entire useful state is just the remaining health of archers $i-1$ and $i$.

That is the whole damn trick.

DP state

Define

$dp(i,u,v)$

as the minimum number of additional shots needed on positions $i$ to $n-1$ if:

• archers $1$ to $i-2$ are already dead,
• archer $i-1$ has remaining health $u$,
• archer $i$ has remaining health $v$.

Any negative health is equivalent, so we clip every negative value to $-1$:

$clip(t) = max(-1, t).$

Since every initial health is at most $15$, the only possible stored values are $-1, 0, 1, ..., 15$.

Transition

Assume $i < n-1$ and we fire $x$ times at position $i$.

First, archer $i-1$ must die now, because after this step nobody can touch it anymore. So we require

$u - b x < 0.$

After those $x$ shots:

• archer $i$ becomes $v - a x$,
• archer $i+1$ becomes $h_{i+1} - b x$.

So the next state is

$u' = clip(v - a x), v' = clip(h_{i+1} - b x).$

Hence

$dp(i,u,v) = min (x + dp(i+1,u',v')).$

The minimum is taken over all integers $x$ from $0$ to $16$ such that $u-bx<0$.

Why is $x <= 16$ enough? Because $h_i <= 15$ and $b >= 1$:

$16b > 15, 16a > 15.$

So $16$ shots at one position already kill every archer that position can affect. More than that is pure waste.

Base case

At $i=n-1$ we are deciding the last shootable position. It affects exactly archers $n-2$, $n-1$, and $n$.

So we just need the smallest $x$ such that

$u - b x < 0, v - a x < 0, h_n - b x < 0.$

Equivalently,

$x = max(need(u,b), need(v,a), need(h_n,b)),$

where $need(h,d)=0$ if $h<0$, otherwise $need(h,d)=floor(h/d)+1$.

Why this is correct

Induction on $i$.

At state $(i,u,v)$, every valid solution must choose some number $x$ of shots at position $i$. That choice is valid iff it kills archer $i-1$ now, meaning $u-bx<0$. After choosing $x$, the future no longer cares about anything on the far left; it only needs the remaining health of archers $i$ and $i+1$, which is exactly the next state we compute. So the recurrence checks every possible valid first move and picks the best one.

The base case is obviously correct because only one shootable position remains.

Done. No black magic, just a tiny profile DP.

Reconstruction

Store which value of $x$ gave the best answer for each state. Start from the initial state

$dp(2, h_1, h_2).$

Follow the stored choices, and print index $i$ exactly $x$ times.

Since order does not matter, printing them grouped by position is completely valid.

Complexity

Number of states:

$O(n * 17 * 17).$

Each state tries at most $17$ values of $x$.

So the total complexity is

$O(n * 17^3),$

with memory

$O(n * 17^2).$

That is tiny. The reduced constraints basically hand you this DP on a silver platter.