I first thought that solving
this problem would require much longer piece of code ! Urge you to have a go at this first.
The first thought is to see if each inversion sequence has a one-to-one correspondence with the actual permutation. Given a permutation, its inversion sequence is obviously unique. Other way, if an inversion sequence has two different permutations, then we can start verifying numbers and their positions in ascending order as follows - Suppose x is the lowest number whose position does not match in the two permutations but their inversion sequence is the same. But the higher of the inversion values is not consistent since it must be made of the numbers lower than itself. So the permutation is unique too.
The brutest of brute force ideas for this problem could be to just generate all permutations of the input length and see if the criteria is met.
So the clear next approach is to try generating the permutation by considering the positions in the reverse order. Since the inversion sequence (input) only worries about numbers lesser than the current appearing to the right, we use the reverse ordering while writing out the output permutation. So for the permutation of numbers from 1-8, we should be able to write out the answer by deciding the position of '8' first then descending towards '1'.
At each step, we keep track of how many numbers lie to the right of the current position. And here is the core problem - For a permutation of size 'N' numbers ('N' in 10^^5 range), how to maintain efficiently the relative position-from-the-right for each number while some positions keep getting filled iteratively ? O(N) numbers and O(N) per number meaning overall O(N^^2) is not an option with that large 'N'.
The next option is maintaining an augmented balanced R-B Tree wherein each node keeps the count of nodes under it. Too long and complex to code...
Another data structure that comes to mind is a
Binary Indexed Tree - BIT . This will help fill up a position and then update the relative positions appropriately in O(N.log N) time. This would require referring to some known implementations.
Somehow I felt that this should require something less than a BIT in full generality. Basically I got this -
1. Start with an array of size 'N' filled with values equal to the initial relative position from the right. So the values are in descending order from '(N - 1)' towards '1'.
2. Going iteratively in reverse order as thought earlier, do a modified binary search for the right position.
3. During the binary search, whenever going right, mark the current node to say that its relative position will reduce by '1' since we are on the way to fill up a position towards it's right.
4. When traversing to the left, increment the position that is sought since we know that those many positions to the right have been occupied !
5. When the correct position is found (sought position matches the calculated position), mark that position as deleted but nothing to delete from the array or shift values.
This takes O(log N) time for each of the number being placed with an overall O(N.log N)...
Here is the "accepted" code I got,
#include <iostream>
#include <vector>
class Position{
public:
int pos;
int change;
bool deleted;
Position():change(0), deleted(false){
}
};
int bin_search(std::vector<position>& vecpos, int seek, int left, int right){
if(right <= left){
vecpos[left].deleted = true;
++vecpos[left].change;
return left;
}
int mid = left + (right - left) / 2;
int curr = vecpos[mid].pos - vecpos[mid].change;
if(vecpos[mid].deleted == false && seek == curr){
vecpos[mid].deleted = true;
++vecpos[mid].change;
return mid;
}
if(seek > curr){
return bin_search(vecpos, seek + vecpos[mid].change, left, mid - 1);
}
else{
++vecpos[mid].change;
return bin_search(vecpos, seek, mid + 1, right);
}
}
int main(){
int N;
std::cin >> N;
std::vector<int> inv(N);
std::vector<position> vecpos(N);
std::vector<int> ans(N);
for(int i = 0; i < N; ++i){
std::cin >> inv[i];
vecpos[i].pos = N - i - 1;
}
for(int i = N - 1; i >= 0; --i){
int pos = bin_search(vecpos, inv[i], 0, N - 1);
ans[pos] = i + 1;
}
for(int i = 0; i < N; ++i){
std::cout << ans[i];
if(i < N - 1)
std::cout << " ";
}
std::cout << "\n";
return 0;
}
This works because for any 'leaf' node position, we always use the same binary search traversal !
It's always interesting to see patterns linking linear structures like arrays with hierarchical ones like trees.
The connection almost always requires something novel.
