yesterday I had a coding interview in which I was asked the following problem which I was not able to solve. please help me to figure out an approach for this problem.
Problem: Alex has a permutation of first n natural numbers in an array A for this permutation he has calculated another array B which is done as follows
B[i] will contain the number of elements on left of index i which are bigger then a[i], now somehow Array A is lost then we have to regenerate the array A from array B.
This problem is quite similar to https://codeforces.net/contest/1208/problem/D
You can initialise all elements of a Fenwick tree to 1 and binary search for the value while traversing array B from right to left and updating the found value to 0.
Thank you.
You can determine the last element as n — b[n]. Now proceed from the back and keep a track of the used up elements and the available elements and check if placing a given value satisifies the constraint. Naively I think it can be done in O(n ^ 2) and then optimise using sets.
The assertion I think would be that the permutation is unique as at any stage our invariant is that there is a finite list and only placing a particular element would satisfy the constraint. The invariant holds vacuously at the end(pos = n) and hence it will hold at termination as well
oh i was close to this but I got distracted from this approach.
You can use a segment tree to mark the visited elements as 0(set all indices of segment tree to 1 initially) and then query for sum range in segment tree whose value is b[i] while traversing b from back.
Sorry for my English.
thanks for sharing.
You can solve it from the rightmost element using fenwick/segment tree + binary search in
O(n log^2(n)).Another alternatives is to use pbds or bbst and then solve them in
O(n log(n)).