CEOI 2018 Global Warming (Gold LIS Module)

Hi, I tried out the CEOI 2018 problem and I was confused about one section on the internal editorial. (Editorial: https://usaco.guide/problems/ceoi-2018global-warming/solution).

The editorial claims that one should define f[i] as the LIS that ends on a[i] and g[i] as the longest decreasing subsequence that ends on a[i] after [1,i] has been modified (minus x). And the solution equals max(f[i] + g[i] - 1) for i \in [1,N].

However, I was instead thinking to change the definition of g[i] as the longest decreasing subsequence that ends on a[i] without any modifications. And the solution equals max(f[i] + g[i+1]) for all i that satisfies a[i] - d < a[i+1] (so that the two LIS can be linked together). This algorithm doesn’t pass though. I would like to ask why? (Small test cases that make my algorithm produce an incorrect answer would also help). Thanks.

My Full Code:


#include <bits/stdc++.h>
#define INF 1e9+5
#define pb push_back
using namespace std;
 
const int maxN = 2e5+5;
 
int a[maxN];
int f[maxN]; //length of LIS that ends on a[i]
int g[maxN]; //Length of longest decreasing subsequence that ends at a[i]
int N,d;
 
bool cmp(const int &a, const int &b){return a > b;}
 
void testIO(){
    freopen("../test.in","r",stdin);
    return;
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //testIO();
    cin >> N >> d;
    for(int i = 1; i <= N; ++i)cin >> a[i];
    a[0] = -1;
    //Calculate f
    f[0] = 0;
    vector<int> dp;
    for(int i = 1; i <= N; ++i){
        int pos = lower_bound(dp.begin(),dp.end(),a[i]) - dp.begin();
        if(pos == dp.size())
            dp.pb(a[i]);
        else dp[pos] = a[i];
        f[i] = pos + 1;
    }
    //Calculate g
    g[N+1] = 0;
    dp.clear();
    for(int i = N; i >= 1; --i){
        int pos = lower_bound(dp.begin(),dp.end(),a[i],cmp) - dp.begin();
        if(pos == dp.size())
            dp.pb(a[i]);
        else dp[pos] = a[i];
        g[i] = pos + 1;
    }
    //Calculate answer
    int res = 0;
    for(int i = 0; i <= N; ++i){
        if(a[i] - d < a[i+1]){
            res = max(res, f[i] + g[i+1]);
        }
    }
    cout << res << '\n';
    return 0;
}

Try
6 9 420 1 1 1 1 1 1 1 2 3

Should be clear why.

As a followup to this problem, I believe it should also be solvable via segment tree, and can be generalized to K removes, with complexity of O(N log(N) K). Keep a dp array(length K) of segment trees. Each segment tree(length N) has all the values in the array, coordinate compressed. As we iterate from left to right, dp[k][val_at_i] = 1+max(max(all values of dp[k-1]), max(dp[k][0]… dp[k][val_at_i - 1]).

Can someone confirm or disprove this idea?

Yea I see the issue now, thanks.

np