Sahilamin219's blog

Google Question Asked Onsite
By Sahilamin219, history, 2 years ago, In English

count array : for a given array it stores, for each ith element number of element greater than it's value from the left.

For a given number N , there exits an permutation array (1,N) such that it gives you same count array. You are given an count array and you have to find original array.

Example : count array => 0 0 0 1 2 0

then original array would be => 1 2 5 4 3 6

Required Solution was Nlog(N).

Hope the question is clear, if there's any doubt plz comment.

For my person experience click here

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +13 Vote: I do not like it

Initialise an ordered_set containing integers from 1 to N. You'll be constructing the original array in reverse, because we can make this observation: Consider the element with index N, we know that all the other numbers of the permutation are to the left of it, we can now deduce which number it is thanks to count_array[N]. The log(N) part of the complexity comes from searching in the ordered_set using find_by_order() and removing every element we find so far.

Solution
→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

First of all, only the order of the elements does matter, the values themselves don't, so this array 1 2 3 4 is equivalent to this 1 3 4 6.

if cnt[i] = x means that we can shift the subarray (i, i-x) by 1. For example

Permu : 1 2 3 4 5 6

Count : x x x x 2 x

Permu :1 2 4 5 3 6

The subarray $$$[1,i-1]$$$ still has the same sorted order (only order does matter).

So how to do this shifting efficiently? Because the subarray is still sorted, and let k be $$$count[i]$$$, then $$$Permu[i] =$$$ the $$$k_{th}$$$ largest value in the current subarray which can be found using ordered_set (PBDS).

Code
→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    How about doing something like this : finding first zero from right, the element at this index(suppose ith) is bound to be current_max available. Then we can decrease array[i+1,n] by 1. And now current_max available will be decreased by 1 and also replace ith element by INF. Range update of (i,n) can be done by lazy seg trees and rightmost 0 can also be found using seg tree. TC : O(nlogn) Is there a better way to do update of (i,n) by -1 ?

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I didn't understand, why do we care about cur_max?

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        because cur_max will be filled at rightmost 0 in every iteration.(i meant in permutaion array)

        arr: 0 0 0 1 2 0 0 0 0 1 2 6 0 0 5 0 1 6 0 0 5 4 0 6 0 0 5 4 3 6 0 2 5 4 3 6 1 2 5 4 3 6 by current_max i simply meant unused max.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          IDK if it's working, but can you prove this solution?

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, hide # ^ |
             
            Vote: I like it +1 Vote: I do not like it

            suppose currently in count array there r multiple 0s. Then max element available must be placed at rightmost pos, because if we place at any other place, condition for 0s after that index can't be satisfied. Second, once we place the element at ith(rightmost 0), we have placed one greater element to all pos in its right, so decrease (i+1,n) by 1 in count array. If u think it's wrong, a counter case will be highly welcome.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              Yup got u. This might work. Write a code and pass it to me

              some cases I wrote:

              3
0 1 1
3 1 2

4
0 1 0 2
3 1 4 2

4
0 1 2 3
4 3 2 1
              → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +10 Vote: I do not like it

    are data structures like ordered set permitted to use in interviews?

    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/B

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It’s a standard segment tree problem of generating the permutation using inversion array.

→ Reply