11AUnreviewed900GPT-5.5 (high)

Increasing Sequence

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

constructive algorithms implementation math

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Process the sequence from left to right. Once you decide the final value of $b_{i-1}$ , the only thing $b_i$ cares about is being strictly larger than that.

There is never a reason to increase an element more than necessary. Extra increases only make life harder for the next elements. Greedy isn't just okay here — it's begging to be used.

For each $i$ , if $b_i > b_{i-1}$ after previous fixes, do nothing. Otherwise, add $d$ some number of times until $b_i > b_{i-1}$ .

If the current adjusted previous value is $p$ and current value is $x \le p$ , you need the smallest integer $k$ such that

x + k d > p.

Rearrange this with integer division.

The exact number of moves for position $i$ when $b_i \le b_{i-1}$ is

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

Add $k$ to the answer and replace $b_i$ by $b_i + kd$ .

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:

It uses the fewest moves for position $i$ .
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.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int n;
    ll d;
    cin >> n >> d;

    vector<ll> b(n);
    for (ll &x : b) cin >> x;

    ll ans = 0;

    for (int i = 1; i < n; i++) {
        if (b[i] <= b[i - 1]) {
            ll moves = (b[i - 1] - b[i]) / d + 1;
            ans += moves;
            b[i] += moves * d;
        }
    }

    cout << ans << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int n;
    ll d;
    cin >> n >> d;

    vector<ll> b(n);
    for (ll &x : b) cin >> x;

    ll ans = 0;

    for (int i = 1; i < n; i++) {
        if (b[i] <= b[i - 1]) {
            ll moves = (b[i - 1] - b[i]) / d + 1;
            ans += moves;
            b[i] += moves * d;
        }
    }

    cout << ans << '\n';
    return 0;
}

View on Codeforces Back to the list