# 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;
}
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