Restore a Permutation from Greater-Right Counts
National Olympiad — Regional round (2020 season)
Submission name: restore.cpp
Problem summary
A permutation of 1…n is encoded by b[i], the number of later values greater than a[i]. Recover the unique permutation.
Input
n and n valid greater-right counts.
Output
The recovered permutation.
Constraints
2 ≤ n < 100000; 0 ≤ b[i] < 100000; input describes a valid permutation.
Worked example
Input and output for the worked example discussed below.
Input
6 2 3 0 0 1 0
Output
4 2 6 5 1 3
Solution analysis
- Process positions left to right while retaining the set of unused values. Every unused value except the one chosen now will be to its right.
- With r values remaining, the chosen value must be the (r−b[i])-th smallest. A Fenwick tree contains one for each unused value and zero for removed ones; binary lifting selects the required rank in O(log n).
- Initially r=6,b=2 selects value 4. Removing it leaves five values; b=3 then selects the second smallest,2. Continuing gives 4,2,6,5,1,3.
Why it works
The rank leaves exactly b[i] larger unused values, determining the unique valid value at each position.
Complexity: O(n log n) time and O(n) space.
Watch out. The rank is remaining−b[i], not b[i]+1. Remove each chosen value and use 1-based Fenwick indices.
Commented C++17 solution
An independently written complete program with standard headers.
// The rank leaves exactly b[i] larger unused values, determining the unique valid value at each position.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int count;
cin>>count;
vector<int>tree(count+1);
for(int index=1;index<=count;index++){
tree[index]=index&-index;
}
int bit=1;
while(bit*2<=count){
bit*=2;
}
for(int position=0;position<count;position++){
int greater;
cin>>greater;
int rank=count-position-greater;
int index=0;
for(int step=bit;step>0;step/=2){
int next=index+step;
if(next<=count&&tree[next]<rank){
rank-=tree[next];
index=next;
}
}
int value=index+1;
if(position>0){
cout<<' ';
}
cout<<value;
for(int update=value;update<=count;update+=update&-update){
tree[update]--;
}
}
cout<<'\n';
}