Overview

We want to modify the elevations of a sequence of checkpoints such that the difference between adjacent elevations is exactly 1, and all elevations are non-negative integers. In this problem, we need to find the maximum number of checkpoints whose current elevations can be kept without modification.

Observation

First, let’s look at what we can infer from the condition: “the absolute difference between adjacent checkpoint elevations is exactly 1”. Let \(H'_i\) be the elevation after adjustment. Then, \(H'_{i+1} = H'_i \pm 1\). In other words, moving to the next checkpoint changes the elevation by either \(+1\) or \(-1\).

Here, if we focus on the parity of \(H'_i + i\), we have: \(H'_{i+1} + (i+1) = (H'_i \pm 1) + i + 1 = (H'_i + i) + (1 \pm 1)\) Since \(1 \pm 1\) is either \(0\) or \(2\), the parity of \(H'_{i+1} + (i+1)\) and \(H'_i + i\) must always match. Therefore, in any valid sequence, the parity of \(H'_i + i\) must be the same for all \(i\). Similarly, for the checkpoints whose original elevations \(H_i\) are kept, the parity of \(H_i + i\) must be uniform. Thus, we can divide the checkpoints into two groups based on the parity of \(y_i = i + H_i\) and consider them independently.

Next, let’s consider the condition for keeping checkpoints. Suppose we keep two checkpoints \(i\) and \(j\) (\(i < j\)) as they are. Since the elevation can only change by \(\pm 1\) per step, the elevation difference \(|H_j - H_i|\) between \(i\) and \(j\) cannot exceed the number of steps \(j - i\). That is, we must have: \(|H_j - H_i| \le j - i\) Expanding this absolute value yields two inequalities: 1. \(H_j - H_i \le j - i \Rightarrow i - H_i \le j - H_j\) 2. \(H_i - H_j \le j - i \Rightarrow i + H_i \le j + H_j\)

If we define \(x_i = i - H_i\) and \(y_i = i + H_i\), these conditions can be written as \(x_i \le x_j\) and \(y_i \le y_j\). This reduces to the problem of finding the longest subsequence of points \((x_i, y_i)\) on a 2D plane such that both the \(x\)-coordinates and \(y\)-coordinates are non-decreasing.

Algorithm

1. For each checkpoint \(i\) (1-indexed), calculate \(x_i = i - H_i\) and \(y_i = i + H_i\).
2. Divide the checkpoints into two groups based on the parity of \(y_i\).
3. In each group, sort the checkpoints in ascending order of \(x_i\). If \(x_i\) is the same, sort them in ascending order of \(y_i\).
4. For each sorted group, find the length of the Longest Increasing Subsequence (LIS) with respect to \(y_i\).
5. The maximum of the LIS lengths obtained from the two groups is the answer.

Complexity

• Time Complexity: \(O(N \log N)\) overall, as sorting and LIS computation can both be done in \(O(N \log N)\) time.
• Space Complexity: \(O(N)\) to store the information for each checkpoint.

Implementation Details

• Multiple points with the same \(x_i\) value can be kept simultaneously (since we can set the intermediate elevations to increase or decrease by 1 at each step).

• When finding the LIS, to prevent incorrectly counting or failing to select multiple points with the same \(x_i\), the secondary sorting key must be the ascending order of \(y_i\). This ensures that points with the same \(x_i\) are ordered non-decreasingly with respect to \(y_i\), allowing them to be correctly counted as elements of the LIS.

• Although the provided code is written in C++ and uses upper_bound to find the strictly increasing LIS, notice that if \(y_i = y_j\), then we must have \(x_i = x_j\). Thus, there are no distinct points with the same \(y_i\). This means that any sequence satisfying the non-decreasing condition will automatically satisfy the strictly increasing condition as well.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solve_lis(const vector<pair<long long, long long>>& pts) {
    vector<long long> dp;
    for (const auto& p : pts) {
        long long y = p.second;
        auto it = upper_bound(dp.begin(), dp.end(), y);
        if (it == dp.end()) {
            dp.push_back(y);
        } else {
            *it = y;
        }
    }
    return dp.size();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    if (!(cin >> N)) return 0;
    
    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }
    
    vector<pair<long long, long long>> odd_pts, even_pts;
    for (int i = 0; i < N; ++i) {
        long long x = (i + 1) - H[i];
        long long y = (i + 1) + H[i];
        if (y % 2 == 0) {
            even_pts.push_back({x, y});
        } else {
            odd_pts.push_back({x, y});
        }
    }
    
    auto cmp = [](const pair<long long, long long>& a, const pair<long long, long long>& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    };
    
    sort(even_pts.begin(), even_pts.end(), cmp);
    sort(odd_pts.begin(), odd_pts.end(), cmp);
    
    int ans_even = solve_lis(even_pts);
    int ans_odd = solve_lis(odd_pts);
    
    cout << max(ans_even, ans_odd) << "\n";
    
    return 0;
}

---

This editorial was generated by or-glm5.2-high.