Lengths of Next-Greater Chains
Autumn Tournament (2017)
Submission name: chain.cpp
Problem summary
For every position, repeatedly jump to the first strictly greater value to its right. Print how many jumps that chain makes; the starting position itself is not counted.
Input
N, followed by N positive integers.
Output
N chain lengths in index order.
Constraints
0 < N < 500000; 0 < ai < 1000000.
Worked example
Original statement sample.
Input
11 3 2 4 2 11 2 7 5 8 10 6
Output
2 2 1 1 0 3 2 2 1 0 0
Solution analysis
- Process indices from right to left. Maintain a stack of possible next-greater positions. Pop every top whose value is at most the current value: that position cannot answer the current query, and the current, closer position will dominate it for future queries.
- After these pops, the top is the nearest strictly greater element on the right. Its chain length is already known, so length[i]=1+length[top]. If the stack is empty, no jump exists and length[i]=0. Push i after computing its answer.
- In the sample, position6 has value2. Its first jump reaches7 at position7, then8 at position9, then10 at position10. The length is3. A value10 at position10 has no greater value to its right and receives0. Equal values must be popped because the comparison is strict.
Why it works
The stack removes only dominated candidates: a popped value is no larger than a nearer candidate. Every retained first-greater answer is therefore the closest qualifying position. Right-to-left induction then proves the chain recurrence, since each chosen next position has already been solved.
Watch out. Use <= in the pop condition, not <. Count jumps, not vertices. A decreasing sequence has all answers0; an increasing sequence has lengths N−1,...,0.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>values(n),length(n),pending;
for(int&value:values){
cin>>value;
}
for(int i=n-1;i>=0;--i){
// A closer value at least as large dominates the popped candidate.
while(!pending.empty()&&values[pending.back()]<=values[i]){
pending.pop_back();
}
if(!pending.empty()){
length[i]=length[pending.back()]+1;
}
pending.push_back(i);
}
for(int i=0;i<n;++i){
if(i>0){
cout<<' ';
}
cout<<length[i];
}
cout<<'\n';
}