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