Overview

This problem asks us to maximize the number of points whose elevation remains unchanged (= minimize the number of points whose elevation is changed) among the given mountain elevations. The condition “the maximum elevation decrease in one step is at most \(K-1\)” can be reduced to the Longest Increasing Subsequence (LIS) problem through a variable transformation.

Analysis

1. Organizing the Condition for Not Feeling Fear

The condition for Takahashi not to feel fear when moving from point \(i\) to point \(i+1\) is that the elevation decrease is less than \(K\). Since all elevations are integers, this is equivalent to the decrease being at most \(K-1\). Setting \(D = K - 1\), the condition can be expressed as follows:

\[H_i - H_{i+1} \leq D \iff H_{i+1} \geq H_i - D\]

2. Condition Between Points Multiple Steps Apart

Suppose we select several points to leave unchanged. Let \(i\) and \(j\) (\(i < j\)) be the indices of two adjacent “unchanged points.” What condition is necessary to freely modify the elevations of points \(i+1, \ldots, j-1\) between them so that the entire traversal can be made without feeling fear?

Since the elevation can decrease by at most \(D\) per step, in \(j - i\) steps the elevation can decrease by at most \((j - i)D\). Therefore, the following condition is required:

\[H_j \geq H_i - (j - i)D\]

Conversely, if this condition is satisfied, by setting the elevations of intermediate points as \(H_k = \max(0, H_i - (k - i)D)\), we can always keep the decrease per step within \(D\) while reaching point \(j\) (since there is no limit on elevation increase, it doesn’t matter if the elevation reaches \(0\) along the way).

3. Simplification Through Variable Transformation

Let’s rearrange the condition above:

\[H_j \geq H_i - j \cdot D + i \cdot D\]

\[H_j + j \cdot D \geq H_i + i \cdot D\]

Here, for each point \(i\), we define a new value \(A_i = H_i + i \cdot D\) (1-based index). Then, the condition becomes a very simple form:

\[A_j \geq A_i\]

This means that “the values of \(A\) corresponding to the indices of unchanged points must be non-decreasing (equal to or greater than the previous).”

4. Reduction to Longest Increasing Subsequence (LIS)

Minimizing the number of changed points is equivalent to maximizing the number of unchanged points \(M\). Since points \(1\) and \(N\) cannot be changed, they are always included in the “unchanged points.”

Therefore, the problem can be rephrased as follows: - Find the maximum length \(M\) of a non-decreasing subsequence of \(A\) that starts at \(A_1\) and ends at \(A_N\).

If \(A_1 > A_N\), it is impossible regardless of how elevations are changed, so the answer is -1. Otherwise, we select intermediate elements \(A_i\) (\(1 < i < N\)) satisfying \(A_1 \leq A_i \leq A_N\) to construct a non-decreasing subsequence. Once the maximum length \(M\) is found, the minimum number of points to change is \(N - M\).

Algorithm

The maximum length of a non-decreasing subsequence can be found in \(O(N \log N)\) using dynamic programming (DP) with binary search.

1. Set \(D = K - 1\) and compute \(A_i = H_i + (i + 1) \cdot D\) for each \(i\) (\(0 \leq i \leq N-1\)) (multiplying by \(i+1\) to adjust for 0-indexed).
2. If \(A_0 > A_{N-1}\) (i.e., the original \(A_1 > A_N\)), output -1 and terminate.
3. Prepare a DP array dp. dp[len] represents “the minimum tail value of a valid subsequence of length len + 1.” Initialize all values to \(\infty\) and set dp[0] = A_0.
4. For each \(i = 1, 2, \ldots, N-2\), only if \(A_0 \leq A_i \leq A_{N-1}\) is satisfied, perform the following update:
   • Use binary search (bisect_right) to find the number of elements in the dp array that are at most \(A_i\), and update the value at that position (index idx) with \(A_i\).
5. Finally, use binary search to find the maximum length at which \(A_{N-1}\) can be appended to the end of the subsequence. Let this length be \(M\), then the answer is \(N - M\).

Complexity

• Time Complexity: \(O(N \log N)\) Since binary search (bisect_right) is performed once for each element, the overall complexity is \(O(N \log N)\), which is well within the time limit even for \(N = 3 \times 10^5\).
• Space Complexity: \(O(N)\) The memory required to store array \(A\) and the DP array is \(O(N)\).

Implementation Notes

• Handling Boundary Conditions: Since points \(1\) and \(N\) (i.e., A[0] and A[N-1] in the code) cannot be changed, when selecting intermediate elements \(A_i\), they must fall within the range \(A_0 \leq A_i \leq A_{N-1}\). By ignoring elements that do not satisfy this condition, the endpoint constraints are correctly reflected.

• Non-Decreasing (Weakly Increasing): Since consecutive equal values are allowed, we use bisect_right instead of bisect_left for binary search. This correctly extends the subsequence length when the same value appears.

  Source Code

import sys
from bisect import bisect_right

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    H = [int(x) for x in input_data[2:]]
    
    D = K - 1
    
    # A_i = H_i + i * D (1-based index)
    A = [H[i] + (i + 1) * D for i in range(N)]
    
    A_1 = A[0]
    A_N = A[N - 1]
    
    if A_1 > A_N:
        print(-1)
        return
    
    # dp[len] stores the minimum end value of a valid subsequence of length len + 1
    dp = [float('inf')] * (N + 1)
    dp[0] = A_1
    
    for i in range(1, N - 1):
        val = A[i]
        if A_1 <= val <= A_N:
            idx = bisect_right(dp, val)
            dp[idx] = val
            
    idx = bisect_right(dp, A_N)
    ans_len = idx + 1
    
    print(N - ans_len)

if __name__ == '__main__':
    solve()

---

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