War Strategy

We start at base $k$, and every day we get exactly one command before a new soldier appears at $k$. The command can move a whole pile one step, which is the important trick. If you try to track every soldier individually, congrats, you have chosen pain.

Shape of the answer

Suppose we fortify some bases on the left of $k$. If we can fortify a base at distance $5$, then fortifying a base at distance $3$ is never harder. So for maximizing the count, we only care about how many bases we take on each side, not their exact identities.

So the final useful shape is:

• $L$ bases immediately to the left of $k$,
• $R$ bases immediately to the right of $k$,
• base $k$ itself.

The number of fortified bases is:

$1+L+R.$

The side limits are:

$0 \le L \le k-1,$

$0 \le R \le n-k.$

Now we need to know when a pair $(L,R)$ is possible in $m$ days.

One side first

Say we only want $x$ bases on one side.

The optimal strategy is:

1. Wait $x-1$ days, doing useless zero-moves if needed. Now there are $x$ soldiers at $k$.
2. Move all $x$ soldiers one step outward.
3. Move $x-1$ of them one more step, leaving one behind.
4. Move $x-2$ of them one more step, and so on.

This takes:

$x-1+x=2x-1$

days.

Why can't we do better? Because the farthest base needs a soldier moved outward $x$ times, and the $x-1$ bases behind it each need an extra soldier left behind. Sending one brave dude forward early just creates holes behind him, and then you pay to refill those holes later. No free lunch, just logistics being annoying.

Two sides

Now suppose we want $L$ bases on the left and $R$ on the right.

Let:

$d=L+R,$

$x=\max(L,R).$

The longer side is the bottleneck. Build that side first using the one-side convoy idea. While that convoy is moving, new soldiers keep appearing at $k$. Since the other side has length at most $x$, enough soldiers are waiting at $k$ when we need them.

So the minimum number of days is:

$d+x-1 = L+R+\max(L,R)-1.$

This also covers the one-sided case. If $R=0$, then it becomes:

$L+L-1=2L-1.$

If $L=R=0$, the answer is just base $k$, needing $0$ days.

Checking a fixed answer size

Let $d=L+R$ be the number of fortified bases outside $k$.

We want to know if there is a valid split $L+R=d$ such that:

$d+\max(L,R)-1 \le m.$

Rearrange:

$\max(L,R) \le m-d+1.$

Call this value:

$\text{lim}=m-d+1.$

Now $L$ must satisfy all of these:

• $L \ge 0$,
• $L \le k-1$,
• $R=d-L \ge 0$, so $L \le d$,
• $R=d-L \le n-k$, so $L \ge d-(n-k)$,
• $L \le \text{lim}$,
• $R=d-L \le \text{lim}$, so $L \ge d-\text{lim}$.

So possible $L$ values form one interval:

$\max(0, d-(n-k), d-\text{lim}) \le L \le \min(k-1, d, \text{lim}).$

If that interval is non-empty, then $d$ outside bases are possible.

Binary search

If we can fortify $d$ outside bases, then we can definitely fortify fewer. So feasibility is monotonic, and we binary search the maximum $d$.

The final answer is:

$d+1,$

because base $k$ is always fortified at the end of every day by the newly arriving soldier.

Complexity per test case:

$O(\log n).$

That is easily fine.