2202AUnreviewed800

Parkour Design

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

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.

Think about what adding 1 to a contiguous segment [l,r][l, r] does to the adjacent differences di=hi−hi+1d_i = h_i - h_{i+1}. Which differences actually change?

Only the differences at the two boundaries of the segment change: dl−1d_{l-1} decreases by 1 (if l>1l > 1) and drd_r increases by 1 (if r<nr < n). All interior and exterior differences are untouched.

Since interior differences don't change, any position with ∣hi−hi+1∣>k|h_i - h_{i+1}| > k that isn't at a boundary cannot be fixed. If ∣hi−hi+1∣>k+1|h_i - h_{i+1}| > k+1 for any ii, nothing works — answer is 0.

Positions where di=k+1d_i = k+1 force l=i+1l = i+1 (so the left boundary fix brings it to kk). Positions where di=−(k+1)d_i = -(k+1) force r=ir = i. If there are 2+ forced left endpoints or 2+ forced right endpoints, they conflict and the answer is 0.

Case-split on how many forced boundaries exist (0, 1, or 2 total). When an endpoint is free, avoid placing it where it would create a new violation: don't put rr at a position with dr=kd_r = k (would become k+1k+1), and don't put ll where dl−1=−kd_{l-1} = -k (would become −(k+1)-(k+1)). For the "no bad positions" case, count valid (l,r)(l, r) pairs efficiently using a suffix sum over valid right endpoints.

Key Observation

When we add 1 to all elements in segment [l,r][l, r], the adjacent differences di=hi−hi+1d_i = h_i - h_{i+1} change only at the boundaries:

  • Left boundary (i=l−1i = l-1, if l>1l > 1): did_i decreases by 1.
  • Right boundary (i=ri = r, if r<nr < n): did_i increases by 1.
  • Everything else is unchanged.

This is the crux of the problem. Interior elements all get +1, so their mutual differences don't budge.

Classifying Positions

Since we can only shift boundary differences by exactly 1:

  • If ∣di∣>k+1|d_i| > k+1 for any ii: impossible, answer is 00.
  • If di=k+1d_i = k+1 (must-L position at ii): we must have l=i+1l = i+1 so the left boundary reduces it to kk.
  • If di=−(k+1)d_i = -(k+1) (must-R position at ii): we must have r=ir = i so the right boundary brings it to −k-k.

If there are ≥2\ge 2 must-L positions or ≥2\ge 2 must-R positions, they demand conflicting values for the same endpoint → answer is 00.

Four Cases

Case 1: One must-L at aa AND one must-R at bb. The segment is forced to be [a+1,b][a+1, b]. Valid iff a<ba < b, giving answer 1 or 0.

Case 2: One must-L at aa, no must-R. l=a+1l = a+1 is fixed. rr ranges from a+1a+1 to nn, but we must avoid r<nr < n where dr=kd_r = k (since +1+1 would push it over). Count the valid rr values.

Case 3: No must-L, one must-R at bb. Symmetric: r=br = b is fixed. Count valid ll values from 11 to bb, avoiding l>1l > 1 where dl−1=−kd_{l-1} = -k.

Case 4: No bad positions at all. The "do nothing" option always works (+1 to the answer). For non-empty segments [l,r][l, r], we need:

  • l=1l = 1 or dl−1≠−kd_{l-1} \neq -k (left boundary doesn't create a violation)
  • r=nr = n or dr≠kd_r \neq k (right boundary doesn't create one)

These conditions depend independently on ll and rr (with the constraint l≤rl \le r). We compute a suffix sum of valid right endpoints and sweep over valid left endpoints.

Why No Cross-Contamination?

A natural worry: "what if the left boundary creates dl−1=kd_{l-1} = k and then it's also somehow the right boundary?" But l−1<l≤rl-1 < l \le r, so the left and right boundary positions are always distinct. Boundary effects don't interfere with each other.

Complexity

O(n)O(n) per test case — one pass to classify, one pass to count.

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

using ll = long long;

void setIO(const string& name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef ZK_LOCAL_RUN
    freopen("f.in", "r", stdin);
    freopen("f.out", "w", stdout);
#else
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

int main() {
    setIO();
    int t;
    cin >> t;
    while (t--) {
        int n;
        ll k;
        cin >> n >> k;
        vector<ll> h(n);
        for (auto& x : h) cin >> x;

        if (n == 1) {
            // No adjacent pairs => everything works: do nothing + [1,1]
            cout << 2 << "\n";
            continue;
        }

        int m = n - 1;
        vector<ll> d(m);
        for (int i = 0; i < m; i++) d[i] = h[i] - h[i + 1];

        // If any |d[i]| > k+1, no single +1 segment can fix it
        bool impossible = false;
        for (int i = 0; i < m; i++) {
            if (abs(d[i]) > k + 1) { impossible = true; break; }
        }
        if (impossible) { cout << 0 << "\n"; continue; }

        // must-L: d[i] = k+1 => need l = i+1
        // must-R: d[i] = -(k+1) => need r = i
        vector<int> mustL, mustR;
        for (int i = 0; i < m; i++) {
            if (d[i] == k + 1) mustL.push_back(i);
            if (d[i] == -(k + 1)) mustR.push_back(i);
        }

        if ((int)mustL.size() > 1 || (int)mustR.size() > 1) {
            cout << 0 << "\n";
            continue;
        }

        if (mustL.size() == 1 && mustR.size() == 1) {
            int a = mustL[0], b = mustR[0];
            // Segment must be [a+1, b], valid iff a < b
            cout << (a < b ? 1 : 0) << "\n";
        } else if (mustL.size() == 1) {
            // l fixed at mustL[0]+1, count valid r values
            int l = mustL[0] + 1; // 0-indexed
            ll cnt = 0;
            for (int r = l; r < n; r++) {
                // Right boundary: if r < n-1, d[r] must not equal k
                if (r == n - 1 || d[r] != k) cnt++;
            }
            cout << cnt << "\n";
        } else if (mustR.size() == 1) {
            // r fixed at mustR[0], count valid l values
            int r = mustR[0]; // 0-indexed
            ll cnt = 0;
            for (int l = 0; l <= r; l++) {
                // Left boundary: if l > 0, d[l-1] must not equal -k
                if (l == 0 || d[l - 1] != -k) cnt++;
            }
            cout << cnt << "\n";
        } else {
            // No bad positions
            // Suffix count of valid right endpoints
            vector<ll> suf(n + 1, 0);
            for (int r = n - 1; r >= 0; r--) {
                suf[r] = suf[r + 1] + (r == n - 1 || d[r] != k ? 1 : 0);
            }
            ll ans = 1; // "do nothing" option
            for (int l = 0; l < n; l++) {
                if (l == 0 || d[l - 1] != -k) {
                    ans += suf[l];
                }
            }
            cout << ans << "\n";
        }
    }
    return 0;
}
View on CodeforcesBack to the list