### SPyofgame's blog

By SPyofgame, history, 2 months ago, #### 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 ?" Comments (8)
 » 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$ nIf 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.
•  » » This or This
•  » » » I found a better solution :D $O(k \sqrt{K})$ here
•  » » » » 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, # ^ | ← Rev. 2 →   But a red-ranker in VNOI suggested me to read this :D
•  » » » » Because my compile time seems to be faster
•  » » » » » If $N$ is much larger then $\sqrt{K}$ then shouldnt it be $O(K \sqrt{K})$ an better approach ?
 » 7 weeks ago, # | ← Rev. 2 →   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.