Reconstruct Covered Towers
National Olympiad — National round
Submission name: cover.cpp
Problem summary
Recover a permutation p of 1…N from counts Lᵢ. Tower i covers tower j when j<i, pⱼ<pᵢ, and no index k with j<k<i has pₖ>pⱼ. Lᵢ specifies how many towers i covers.
Input
N, followed by N counts Lᵢ.
Output
Any valid permutation, one height per line.
Constraints
2 ≤ N ≤ 10,000; a solution is guaranteed; Lᵢ are nonnegative.
Worked example
An independently prepared example for this explanation.
Input
3 0 0 2
Output
2 1 3
Solution analysis
- A decreasing stack of visible tower heights loses exactly Lᵢ top entries when tower i arrives.
- For every popped vertex j add constraint pⱼ<pᵢ. If a stack top remains, add pᵢ<p_top. Push i.
- Topologically order these constraints and assign increasing heights 1…N.
Why it works
The stack after each prefix contains exactly its right-to-left maxima. Precisely its initial smaller top entries are covered by the new tower. The inequalities force the specified pops, and guaranteed feasibility makes the constraint graph acyclic.
Watch out. This is not the number of all earlier shorter towers; intervening taller towers block coverage.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The stack after each prefix contains exactly its right-to-left maxima. Precisely its
// initial smaller top entries are covered by the new tower.
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
int main(){
int n;
cin>>n;
vector<vector<int>>g(n);
vector<int>deg(n),st,ans(n);
auto edge=[&](int a,int b){
g[a].push_back(b);
deg[b]++;
};
for(int i=0;i<n;i++){
int k;
cin>>k;
while(k--){
edge(st.back(),i);
st.pop_back();
}
if(!st.empty()){
edge(i,st.back());
}
st.push_back(i);
}
queue<int>q;
for(int i=0;i<n;i++){
if(!deg[i]){
q.push(i);
}
}
int rank=0;
while(!q.empty()){
int v=q.front();
q.pop();
ans[v]=++rank;
for(int u:g[v]){
if(!--deg[u]){
q.push(u);
}
}
}
for(int x:ans){
cout<<x<<'\n';
}
}