Smallest Inequality Permutation
National Olympiad — National round
Submission name: perm.cpp
Problem summary
Find the lexicographically smallest permutation of 1…N satisfying the supplied inequality between each neighboring pair.
Input
N, then a string of N−1 characters < or >.
Output
The permutation, separated by spaces.
Constraints
1 < N ≤ 500,000.
Worked example
An independently prepared example for this explanation.
Input
4 >><
Output
3 2 1 4
Solution analysis
- Start with 1,2,…,N.
- For every maximal consecutive run of > signs, reverse the corresponding block of values, including both endpoint positions.
Why it works
A decreasing block of length t requires t distinct values. Giving it the t smallest unused values minimizes its first value; their decreasing arrangement is forced. Consecutive blocks separated by < then fit in ascending value ranges.
Complexity: O(N) time, O(N) space.
Watch out. A run of t signs covers t+1 numbers.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: A decreasing block of length t requires t distinct values. Giving it the t smallest unused
// values minimizes its first value; their decreasing arrangement is forced.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<tuple>
#include<numeric>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin>>n>>s;
vector<int>a(n);
iota(a.begin(),a.end(),1);
for(int i=0;i<n-1;){
if(s[i]=='<'){
i++;
continue;
}
int j=i;
while(j<n-1&&s[j]=='>'){
j++;
}
reverse(a.begin()+i,a.begin()+j+1);
i=j;
}
for(int i=0;i<n;i++){
cout<<a[i]<<(i+1==n?'\n':' ');
}
}