SPyofgame's blog

Number of nth permutations with k inversion pairs
By SPyofgame, history, 4 years ago, In English

Simplest way:

Approach
Brute-force <TLE> - O(n! * n ^ 2) time - O(n) space

Improving the algorithm

Approach
BIT, Binary-search, Dynamic-programming <TLE> - O((n! * n + n) log n) time - O(n) space

Using formula to improve furthur more

Approach
Recursive Dynamic Programming Approach <AC> - O(n * k) time - O(n * k) space
Iterative Dynamic Programming Approach <AC> - O(n * k) time - O(k) space

I solved this problem but I wonder if there is a better way (faster than $$$O(n \times k)$$$)

So my question is "Is there a faster approach for this problem ?"

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

Comments Comments (13)
| Write comment?
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I think O(NK) is the best solution.

Let f(n,c) be the number of sequences of length n with confusion c.

The number of such sequences that start with the number 1 is f(n−1,c) because the 1 does not affect the confusion of the rest of the sequence and it makes no difference if we use numbers 1 $$$\to$$$ n-1 or 2 $$$\to$$$ n

If 1 is the second number, then f(n,c) = f(n−1,c−1) because whichever element is first, it will form a confused pair with the 1. It's easy to see that the complete relation is: .

$$$\underset{i \in [0, n)}{\Sigma}f(n-1)(c-i)$$$

The time complexity of a direct implementation of this formula (using dynamic programming) would be O($$${N}^{2}$$$ C). We need to note that f(n,c) = f(n,c−1) + f(n−1,c) − f(n−1,c−n), which leads to a O(NC) solution. It is also possible to cut down on the memory used by keeping only two rows of the matrix used for calculations at any time.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    This or This

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

      I found a better solution :D $$$O(k \sqrt{K})$$$ here

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

        Are you sure about that? I remember that you often read the wrong subject so often now that you read this tutorial wrong can happen too

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

        Because my compile time seems to be faster

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

          If $$$N$$$ is much larger then $$$\sqrt{K}$$$ then shouldnt it be $$$O(K \sqrt{K})$$$ an better approach ?

          → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Check this post, look at the solution to Perfect Permutations by generating functions. Apart from zscoder's other blog on DP which also has a (slower) solution to this problem, I've also found this solution by Roundgod interesting (solution to K-inversion permutations). In short, this is a well-known, well-discussed problem.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -49 Vote: I do not like it

is there an simpler explanation. I am getting confused by mathematical equations

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +67 Vote: I do not like it

    Yes, by checking AC codes on CC long ongoing contest

    → Reply
»
4 years ago, # |
  Vote: I like it -45 Vote: I do not like it

So my question is "Is there a faster approach for this problem ?"

Just say that you want a solution for the ongoing CC Long Challenge

→ Reply