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

Автор RazvanD, история, 8 лет назад, По-английски

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.

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

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

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

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

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

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

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

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

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

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

            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.

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

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

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

    Thanks!