SPyofgame's blog

By SPyofgame, history, 2 months 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

»
2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 weeks 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

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because my compile time seems to be faster

        • »
          »
          »
          »
          »
          7 weeks 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 ?

»
7 weeks 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.