Is there an efficient way to solve this problem?

Question

Given a series of n numbers, I need an algorithm that runs in worst case O(n*k) to figure out how many arrangements of those n numbers will give me a score of exactly k.

Note that the series does not contain duplicate elements.

The score of a series of numbers is calculated by the number of smaller numbers an element in the series has before it.

For example, The score of the below series would be:

series = [5,3,6]

5 has no smaller number before it, so 0

3 has no smaller number before it, so 0

6 has 2 smaller numbers before it (5,3) so 2

Adding all of this, we get a total score for the series as 2.

What I have tried to do:

I have tried to find all possible arrangements of the series -> (n! many arrangements)

and count the ones that have a score of k.

But this has a worst case time complexity of O(n!). Any help/ideas will be much appreciated. Thanks!

Answer 1

Note that the values contained in the series are not important, and you can consider those values are exactly $1, 2, …, n$ (because only relative order is important).

Denote $A(n, k)$ the number of arrangements of $n$ values to reach score $k$.

Given an arrangement of $n$ values of score $k$, if you add the value $n+1$, you can:

• put it in first position and not change the score;
• put it in second position and add one to the score;
• …
• put it in last position and add $n$ to the score.

Considering all this, we get the induction formula: $$A(n+1, k) = \sum\limits_{i = 0}^n A(n, k - i)$$ The base cases are:

• $A(1, 0) = 1$;
• $A(n, k) = 0$ if $k < 0$.

The total runtime of dynamic programming algorithm computing this would be $\mathcal{O}(n^2k) = \mathcal{O}(n^2)$ if $k$ is considered a constant.

There may be a closed formula that could be used to compute this in $\mathcal{O}(1)$, but I don't know it.