Recovering a Mountain Profile
National Olympiad — Municipal round (2021 season)
Submission name: relef.cpp
Problem summary
Recover heights from adjacent comparisons, knowing differences are±1 and the minimum is zero.
Input
N and N−1 signs < or >.
Output
All N heights.
Constraints
1≤N≤100000.
Worked example
Input and output for the worked example discussed below.
Input
15 <<><<>>>><<><<
Output
1 2 3 2 3 4 3 2 1 0 1 2 1 2 3
Solution analysis
- Start at temporary height zero. Each < increases the next height by one and each > decreases it by one. These are prefix sums of the prescribed changes.
- Track the smallest temporary value, then subtract it from every height. Vertical translation preserves all differences and makes the minimum exactly zero.
- The sample walk reaches temporary minimum−1. Adding one to every height gives the displayed profile. With N=1 there are no signs and the answer is zero.
Why it works
The signs determine every consecutive difference, so all compatible profiles differ by a constant. Subtracting the minimum is the unique shift making the minimum zero.
Complexity: O(N) time and O(N) space.
Watch out. Interpret < as increasing height; handle the empty sign sequence at N=1.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// The signs determine every consecutive difference, so all compatible profiles differ by a constant.
int main(){
int n;
cin>>n;
vector<int>a(n,0);
int lowest=0;
for(int i=1;i<n;i++){
char sign;
cin>>sign;
a[i]=a[i-1]+(sign=='<'?1:-1);
lowest=min(lowest,a[i]);
}
for(int i=0;i<n;i++){
if(i){
cout<<' ';
}
cout<<a[i]-lowest;
}
cout<<'\n';
}