RazvanD's blog

Permheap
By RazvanD, history, 8 years ago, In English

Given an integer n you need to calculate the number of distinct permutations {1, 2, 3, ..., n} such that the permutation represents a linear max heap.

In other words for each position from 1 to n: p[i] > p[2*i] and p[i] > p[2*i+1]

Example: Input: 4 Output: 3

I need help solving this problem, at least a hint please.

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here

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

    Is the runtime O(N) (assume we have preprocessed factorial and modular inverse of factorial) .

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

      No, it's O(NlogN), because the modular inverse is calculated in O(log), atleast I don't know how to do it faster :)

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        If you know , you can find out in O(1). can be computed in O(n).

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

          Ohh yeah I just noticed it now
          (n!) - 1 = (n + 1) * ((n + 1)!) - 1
          Is this correct ?

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

            Yes, that's the recurrence. Another way to do it, using one more array, is to precompute for every i in , then . Here are some ideas to compute inverse efficiently.

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

              I don't think it would be possible to precompute for all i because M can be very large (109 + 7)

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

        Yeah you are right . The preprocessing part takes O(NlogN) , and the part to calculate the number of heaps till N can be done in O(N) using the recurrence that you've posted . So overall it's O(NlogN) .

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

    Thanks!

    → Reply