Aesthetic Tree Heights
National Olympiad — Regional round (2019 season)
Submission name: estet.cpp
Problem summary
Remove trees so that the remaining heights strictly increase, strictly decrease, or first strictly increase and then strictly decrease. Maximize the number kept.
Input
N, followed by N positive heights.
Output
The maximum number of trees that can remain.
Constraints
1 ≤ N ≤ 100,000; 1 ≤ height ≤ 100,000.
Worked example
An independently prepared example for this explanation.
Input
4 2 1 5 3
Output
3
Solution analysis
- For every possible peak i, compute up[i], the longest strictly increasing subsequence ending at i. A standard tails array and lower_bound find these lengths in O(N log N).
- Scan from right to left using the same algorithm to get down[i], the longest strictly decreasing subsequence starting at i. The best bitonic sequence with peak i has up[i]+down[i]−1 elements. A side of length one naturally includes wholly increasing or decreasing answers.
- For 2,1,5,3, the peak 5 has an increasing side of length 2 and a decreasing side of length 2. They share the peak, giving 3. Repeated heights such as 1,5,5 cannot both appear on a strict side.
Why it works
The tails algorithm stores the minimum final value for each achievable increasing-subsequence length; lower_bound finds the largest extendable length and preserves these minima. Reversing the scan obtains decreasing continuations. Any valid sequence has a peak and is bounded by the sum of the two optimal sides at that peak minus one. Conversely those two subsequences lie on opposite sides of the peak and concatenate into a valid sequence, attaining the bound.
Watch out. Use lower_bound rather than upper_bound for strict inequalities. Subtract one because both lengths include the peak.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
// Algorithm: For every possible peak i, compute up[i], the longest strictly increasing
// subsequence ending at i.
using namespace std;
int main(){
int n;
cin>>n;
vector<int>height(n),up(n),down(n),tails;
for(int&value:height){
cin>>value;
}
for(int i=0;i<n;i++){
auto it=lower_bound(tails.begin(),tails.end(),height[i]);
up[i]=static_cast<int>(it-tails.begin())+1;
if(it==tails.end()){
tails.push_back(height[i]);
}
else{
*it=height[i];
}
}
tails.clear();
int answer=0;
for(int i=n-1;i>=0;i--){
auto it=lower_bound(tails.begin(),tails.end(),height[i]);
down[i]=static_cast<int>(it-tails.begin())+1;
if(it==tails.end()){
tails.push_back(height[i]);
}
else{
*it=height[i];
}
answer=max(answer,up[i]+down[i]-1);
}
cout<<answer<<'\n';
}