Overview

This problem involves organizing the given elevation conditions into mathematical expressions under the constraint that Takahashi does not feel fear (i.e., the decrease in elevation is at most \(K-1\)), and reducing it to a variation of the Longest Increasing Subsequence (LIS) problem that maximizes the number of unchanged points.

Analysis

1. Formulating the Condition

The condition for not feeling fear when moving from point \(i\) to \(i+1\) is: $\(H_i - H_{i+1} \leq K - 1\)\( Rearranging this, we get: \)\(H_{i+1} \geq H_i - (K - 1)\)$

This inequality must hold for all adjacent points. Here, using each point’s index \(i\) (1-indexed), we define a new array \(A\) as: $\(A_i = H_i + i \times (K - 1)\)\( Then, the above condition can be rewritten for all \)i\( as: \)\(A_{i+1} \geq A_i\)$ which is an extremely simple non-decreasing (weakly monotonically increasing) condition.

2. Maximizing Unchanged Points

The elevations of point \(1\) and point \(N\) cannot be changed. Therefore, the values of \(A_1\) and \(A_N\) are fixed. For intermediate points \(2, \ldots, N-1\), the elevation can be changed to any non-negative integer.

Since the elevation \(H'_p\) of a changed point \(p\) can be made arbitrarily large, if we let the set of indices of unchanged points be \(\{1, i_2, i_3, \ldots, N\}\), then as long as: $\(A_1 \leq A_{i_2} \leq A_{i_3} \leq \ldots \leq A_N\)$ holds, it is always possible to appropriately set the elevations of the intermediate changed points to make the entire sequence non-decreasing.

Therefore, this problem can be rephrased as follows: “Choose a set of indices of unchanged points \(\{1, i_2, i_3, \ldots, N\}\) satisfying \(A_1 \leq A_{i_2} \leq A_{i_3} \leq \ldots \leq A_N\), and find the maximum number of elements (unchanged points).”

This is nothing other than the problem of finding the Longest Increasing Subsequence (LIS) from array \(A\), extracting elements that are at least \(A_1\) and at most \(A_N\), with the starting point fixed at \(A_1\) and the ending point fixed at \(A_N\).

Algorithm

We use dynamic programming (DP) to find the length of the longest increasing subsequence.

DP Definition

Let \(DP[i]\) be “the maximum number of unchanged points up to point \(i\), when point \(i\) is the last selected (unchanged) point.” - Initial value: \(DP[1] = 1\), all others are \(-\infty\) - Transition: For \(i\) satisfying \(A_1 \leq A_i \leq A_N\), $\(DP[i] = \max_{1 \leq j < i, A_j \leq A_i} (DP[j]) + 1\)\( - **Answer**: If \)DP[N]\( is obtained, the minimum number of changes is \)N - DP[N]\(. If \)DP[N]$ was not updated (unreachable from the starting point), output -1.

Speedup Using Segment Tree

A naive transition takes \(O(N^2)\) time, which will not fit within the time limit (TLE). Therefore, we apply coordinate compression to the values \(A_i\) and use a Segment Tree.

1. Collect values from array \(A\) that are in the range \([A_1, A_N]\), sort them, remove duplicates, and apply coordinate compression.
2. Initialize a segment tree that can retrieve range maximum values, and set \(1\) at the position of \(A_1\).
3. For \(i = 2\) to \(N-1\), do the following:
   • If \(A_1 \leq A_i \leq A_N\) holds, retrieve the maximum value \(val\) from the segment tree over the range \([0, A_i]\).
   • If \(val \geq 1\) (i.e., reachable from starting point \(1\)), set \(DP[i] = val + 1\) and update the segment tree at position \(A_i\) with \(DP[i]\) (taking the \(\max\) with the existing value).
4. Finally, for \(A_N\), similarly retrieve the maximum value \(val\) from the range \([0, A_N]\), and set \(DP[N] = val + 1\).
5. If \(DP[N]\) is a valid value, output \(N - DP[N]\); otherwise, output -1.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting for coordinate compression takes \(O(N \log N)\).
  • Segment tree queries and updates are \(O(\log N)\) per step, giving \(O(N \log N)\) overall.
• Space complexity: \(O(N)\)
  • Array \(A\), the coordinate compression array, and the segment tree use \(O(N)\) memory.

Implementation Notes

• Regarding the non-negative integer constraint: For an intermediate changed point \(p\), the constraint that the elevation must be non-negative \(H'_p \geq 0\) is equivalent to \(A'_p \geq p \times (K-1)\). If \(A_{i_j} \leq A_{i_{j+1}}\) holds between unchanged points \(i_j, i_{j+1}\), then by setting \(A'_p = \max(A_{i_j}, p \times (K-1))\) for intermediate \(p\), we can always construct values that simultaneously satisfy both the non-decreasing property and the non-negative integer constraint. Therefore, comparing only the values of \(A\) is sufficient in the DP transition.

• Segment tree monoid: To retrieve range maximum values, the segment tree operation is max, and the identity element is a sufficiently small value (such as -1e9).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/segtree>

using namespace std;

int op(int a, int b) {
    return max(a, b);
}

int e() {
    return -1e9;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        A[i] = H[i] + (i + 1) * (K - 1);
    }

    if (A[0] > A[N - 1]) {
        cout << -1 << "\n";
        return 0;
    }

    vector<long long> vals;
    for (int i = 0; i < N; ++i) {
        if (A[i] >= A[0] && A[i] <= A[N - 1]) {
            vals.push_back(A[i]);
        }
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto get_pos = [&](long long x) {
        return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
    };

    atcoder::segtree<int, op, e> seg(vals.size());

    int pos0 = get_pos(A[0]);
    seg.set(pos0, 1);

    for (int i = 1; i < N - 1; ++i) {
        if (A[i] >= A[0] && A[i] <= A[N - 1]) {
            int pos = get_pos(A[i]);
            int val = seg.prod(0, pos + 1);
            if (val >= 1) {
                int dp_val = val + 1;
                seg.set(pos, max(seg.get(pos), dp_val));
            }
        }
    }

    int posN = get_pos(A[N - 1]);
    int val = seg.prod(0, posN + 1);
    if (val >= 1) {
        int dp_N = val + 1;
        cout << N - dp_N << "\n";
    } else {
        cout << -1 << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.