Games on the Train

Key observation

Suppose the final equal height is $H$. Then for every tower $i$, the chosen increase is forced:

$$x_i = H - h_i.$$

So the whole game is really just choosing one number $H$.

Now, every tower must be increased exactly once, and each increase must satisfy $x_i \ge 1$. In particular, even the tallest tower cannot stay the same. If

$$M = \max_i h_i,$$

then the final height must satisfy

$$H \ge M + 1.$$

For a fixed final height $H$, the smallest valid $k$ must cover the largest required increase:

$$k \ge \max_i (H - h_i).$$

The largest increase is needed by the shortest tower. Let

$$m = \min_i h_i.$$

Then

$$\max_i(H - h_i) = H - m.$$

So for fixed $H$, we need

$$k = H - m.$$

To minimize $k$, choose the smallest possible $H$, which is $M + 1$. Therefore:

$$\boxed{k = M - m + 1}$$

That’s it. The only tiny trap is forgetting that the tallest tower must also increase by at least $1$. If all towers are already equal, the answer is still $1$, not $0$.

Complexity

For each test case, we just compute the minimum and maximum height.

$$O(n)$$

Since $n \le 5$, this is basically instant. The train will arrive before your CPU notices.