Блог пользователя nipul1

Автор nipul1, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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