Tutorial for CodeForces 1407D

Solution #

First let’s consider the case where $\max(h_{i + 1}, \ldots, h_{j - 1}) < \min(h_i, h_j)$ . $h_i$ could be lower or higher than $h_j$ . There can be multiple $i$ that satisfies the condition and we can observe the leftmost $i$ is the first that $h_i\ge h_j$ , let’s denote this $i_{min}$ , other $i$ between $[i_{min},j]$ must satisfy that $h_i$ is the maximum value among $[i,j-1]$ . This can be solved using monotonic stack. Assume we store the indices in the stack, when adding a new index $j$ , all the indices that will be removed are a valid position to jump to $j$ , so we can do dp and update the minimum number of moves. The time complexity is $O(n)$ .

The second case is similar.

Code #

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int> a(n);
    for(auto& it:a) cin>>it;
    vector<int> dp(n,n);
    dp[0]=0;
    vector<int> h{0},l{0};
    for(int i=1;i<n;i++){
        dp[i]=min(dp[i],dp[i-1]+1);
        while(!h.empty()&&a[i]>=a[h.back()]){
            int x=a[h.back()];
            h.pop_back();
            if(a[i]>x&&!h.empty()) dp[i]=min(dp[i],dp[h.back()]+1);
        }
        while(!l.empty()&&a[i]<=a[l.back()]){
            int x=a[l.back()];
            l.pop_back();
            if(a[i]<x&&!l.empty()) dp[i]=min(dp[i],dp[l.back()]+1);
        }
        h.push_back(i);
        l.push_back(i);
    }
    cout<<dp[n-1];
    return 0;
}