One Insertion for a Consecutive Subsequence
National Olympiad — Municipal round (2024 season)
Submission name: maxseq.cpp
Problem summary
Insert one arbitrary integer anywhere in a sequence. Maximize the length of a subsequence whose consecutive selected values differ by exactly +1.
Source clarification. The PDF header prints 7 January 2023 although Arena assigns the 2024 season.
Input
N, followed by N positive integers.
Output
The maximum achievable subsequence length.
Constraints
1 ≤ N ≤ 500000; 1 ≤ a[i] ≤ 500000.
Worked example
Official statement example.
Input
6 5 1 2 4 5 7
Output
5
Solution analysis
- Maintain plain[v], the best consecutive subsequence ending with value v using only processed input, and used[v], the best ending at v when one inserted element is allowed and has already been used. Process input from left to right.
- For an input value x, a subsequence ending at that occurrence either extends plain[x−1], extends used[x−1], or inserts x−1 immediately before this occurrence after a plain subsequence ending at x−2. The latter option has length plain[x−2]+2. Include length 2 when the inserted value is before the first selected input.
- Take snapshots of predecessor states before updating x. Finally any plain subsequence can gain one by appending its next value after all selected elements, so compare bestPlain+1 too. For 5,1,2,4,5,7 the third transition inserts 3 between 2 and 4, then extends to 5, giving length 5.
Why it works
Every optimal subsequence either ends with its inserted element, covered by bestPlain+1, or ends at an original occurrence x. In the latter case its preceding selected element is original x−1, or is the inserted x−1 preceded by an optional original x−2. These are exactly the transitions. Induction over the processed prefix establishes the stored maxima and hence the final result.
Watch out. This is a subsequence, not a contiguous segment; existing positions may be skipped. An inserted value may be 0.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every optimal subsequence either ends with its inserted element, covered by bestPlain+1,
// or ends at an original occurrence x. In the latter case its preceding selected element is original
// x−1, or is the inserted x−1 preceded by an optional original x−2.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>plain(500003),used(500003);
int answer=1;
for(int i=0;i<n;++i){
int value;
cin>>value;
int x=value+1;
int noInsertion=plain[x-1]+1;
int withInsertion=max(used[x-1]+1,plain[x-2]+2);
plain[x]=max(plain[x],noInsertion);
used[x]=max(used[x],withInsertion);
answer=max(answer,max(plain[x]+1,used[x]));
}
cout<<answer<<'\n';
}