Increasing Sequence

Key observation

We can only increase elements, and each operation adds exactly $d$ to one chosen element.

The sequence must satisfy:

$$b_0 < b_1 < \dots < b_{n-1}.$$

When processing position $i$, all earlier positions are already fixed. In particular, the only condition involving $b_i$ and the past is:

$$b_i > b_{i-1}.$$

So we should make $b_i$ the smallest possible value greater than the already-fixed $b_{i-1}$. Increasing it more is pure self-sabotage: it costs extra moves and makes the next element's job harder. Bad deal.

Greedy strategy

Scan from left to right.

For every $i$ from $1$ to $n-1$:

• If $b_i > b_{i-1}$, it is already fine.
• Otherwise, we need to add $d$ exactly $k$ times so that:

$$b_i + kd > b_{i-1}.$$

We want the smallest such nonnegative integer $k$.

If $b_i \le b_{i-1}$, then:

$$k = \left\lfloor \frac{b_{i-1} - b_i}{d} \right\rfloor + 1.$$

Then update:

$$b_i \leftarrow b_i + kd,$$

and add $k$ to the answer.

Why this is optimal

At index $i$, the previous value $b_{i-1}$ is already fixed and cannot be decreased. Therefore any valid final sequence must make the current value strictly larger than $b_{i-1}$.

Choosing the minimum possible valid value for $b_i$ is optimal because:

1. It uses the fewest moves for position $i$.
2. It gives the smallest possible constraint to position $i+1$.

So the greedy choice is locally optimal and also helps the future. That's the rare kind of greedy that doesn't stab you in the back.

Complexity

We do one pass through the array, and each step does $O(1)$ work.

$$O(n)$$

time and

$$O(1)$$

extra memory, ignoring the input array.