Two Towers

Research note: I checked the Codeforces problem page and the official Kotlin Heroes 14 editorial. The official post’s tutorial text is still loading, but it includes a short accepted-style reference solution, which matches the derivation below. I also checked the Codeforces status page, but it returned an internal error, so the statement remains the source of truth.

Let the required increases be:

$$x=c-a,\qquad y=d-b.$$

If we ignore the special move, the answer is clearly:

$$x+y=(c-a)+(d-b).$$

That is the dumb baseline. Not wrong, just leaving coupons on the floor.

The special move adds one block to both towers in one action. Compared to doing those two increments separately, each special move saves exactly one action. Therefore:

$$\text{answer}= (c-a)+(d-b)-\text{maximum number of special moves}.$$

Now we only need to count how many special moves can possibly be used.

A special move can start only when both towers currently have the same height $h$. Since tower heights only increase, both initial heights must be at most $h$:

$$h\ge \max(a,b).$$

After using the special move, both towers become $h+1$, so both targets must be at least $h+1$:

$$h+1\le \min(c,d).$$

So every special move corresponds to an integer starting height

$$h\in [\max(a,b),\min(c,d)-1].$$

The number of such heights is:

$$k=\max(0,\min(c,d)-\max(a,b)).$$

That gives the formula:

$$\boxed{(c-a)+(d-b)-\max(0,\min(c,d)-\max(a,b))}.$$

Why this is achievable:

1. Raise the lower tower with normal moves until both towers reach height $\max(a,b)$, if possible.
2. Use special moves while both towers can still grow together, up to height $\min(c,d)$.
3. Finish the remaining height on whichever tower still needs blocks using normal moves.

Why it is optimal:

Every special move must start at some equal height $h$. Because heights only increase, these starting heights are all distinct and must lie inside

$$[\max(a,b),\min(c,d)-1].$$

There are only $k$ such heights, so no strategy can use more than $k$ special moves. Since the construction above uses exactly $k$, it is optimal. No hidden DP, no simulation, no weird greedy trap. Just count the valid discount moves.

Edge cases:

• If $a=b=c=d$, then no blocks are needed and the answer is $0$.
• If $\max(a,b)\ge \min(c,d)$, the towers cannot share a useful equal-growing segment, so $k=0$.
• Values up to $10^8$ are easily safe in long long.

Complexity per test case is $O(1)$ time and $O(1)$ memory.