Indian Computing Olympiad

Training Material

Range Queries→From inversions to permutations

Given a permutation that maps each i to P(i), Inversion(i) is the number of j < i that appear to the right of i in the permutation. We can thus associate with each permutation, an inversion sequence. An example is given below. 

                     1  2  3  4  5  6  7  8
Permutation P(i)     2  3  1  6  7  8  4  5
Inversion   I(i)     0  1  1  0  0  2  2  2

How do we recover the permutation from the inversion sequence?

Solution

  1. Start with largest number, here 8. I(8) = 2, so there are two blank space to the right of 8, so we place 8 in position 6. 

    2.                      1  2  3  4  5  6  7  8
                     -  -  -  -  -  8  -  -

  2. Next, omit the position where 8 has been placed and examine I(7) with respect to the remaining seven positions. Since I(7) = 2, 7 has two elements to its right among the seven blank, and hence it goes in slot 5 (slot 6 is already filled by 8). 

    3.                      1  2  3  4  5  6  7  8
                     -  -  -  -  7  8  -  -

  3. Omit the positions where 8 and 7 have been placed and examine I(6). We need to leave two blank, so it goes in slot 5 (slots 5 and 6 are already filled by 7 and 8). 

    4.                      1  2  3  4  5  6  7  8
                     -  -  -  6  7  8  -  -

  4. Omit the positions where 8, 7 and 6 have been placed and examine I(5). We need to leave zero blank, so it goes in the last slot. 

    5.                      1  2  3  4  5  6  7  8
                     -  -  -  6  7  8  -  5

    …

    In general, at each step, use I(j) to determine how many blank slots to leave empty at the right of the current set of slots.

Complexity

In each pass, we have to scan the array to find the kth blank slot remaining. This takes O(N) time, so overall, this takes O(N2) time.

Can we do this in time N log N using a segment tree?

We maintain a segment tree in which we maintain the number of blanks to the right in each interval. Initially, all leaves are empty and the tree looks like this. 

           ---8---
          /       \
         4         4
        /  \      /  \
       2    2    2    2
      /\   /\   /\   /\
     1  1 1  1 1  1 1  1

Now consider I(2) = 1. This tells us that 8 must go in the 3nd blank leaf from the right, or, equivalently, the 6th blank leaf from the left since the value at the root tells us there are totally 8 blank positions available. We walk down to this leaf, set the number of blanks in the interval [6,6] to 0 and propagate the change up. 

          ---7---
         /       \
        4         3
       /  \      /  \
      2    2    1    2
     /\   /\   /\   /\
    1  1 1  1 1  0 1  1
                 |
                 8

Now, we examine I(7) = 2. We need to put it in the 3rd position from the right or, since the root reports 7 blank positions, we need the 5th blank position from the left. The root has only 4 blank leaves on the left, so we have to go right and look for the (5-4) = first blank leaf on the right. Next, walk left and left and, updating intermediate values, we get. 

          ---6---
         /       \
        4         2
       /  \      /  \
      2    2    0    2
     /\   /\   /\   /\
    1  1 1  1 0  0 1  1
              |  |
              7  8

…

In this way, we can insert each number in log N steps into its correct position in the permutation. There are N numbers to insert, so this takes N log N steps.


Problems related to