nipul1's blog

By nipul1, history, 6 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is quite similar to https://codeforces.com/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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh i was close to this but I got distracted from this approach.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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)).