Simplest way:
Iterating all possible nth permutation and count the number of inversion pairs (such pair $$$(a[i], a[j])$$$ that $$$a[i] > a[j]$$$ and $$$i < j$$$)
Count the number of permutations whose number of inversion pairs is $$$k$$$
int n, k;
int inversion_count(const vector<int> &perm) /// count number of inversion in permutation
{
int res = 0;
for (int i = 2; i <= n; ++i)
for (int j = 1; j < i; ++j)
if (perm[i] < perm[j])
res++;
return res;
}
int main()
{
cin >> n >> k;
vector<int> perm(n + 1);
for (int i = 1; i <= n; ++i) /// assigning permutation
perm[i] = i;
int res = 0;
do {
if (inversion_count(perm) == k) /// this permutation is valid (having exactly k inversion pairs)
res++;
} while (next_permutation(1 + all(perm))); /// iterating all possible permutation
cout << res;
}
Improving the algorithm
Using BIT to calculate the number of inversions in $$$O(n log n)$$$
Using Binary-search to find the last position $$$p$$$ that the amount of inversion pair in $$$[1..p]$$$ of this permutation is the same of next permutation
Using Dynamic-programming to ignore the part that has been calculated and recalculating different path
vector<int> BIT;
void inc(int p) { /// increase the amount of visited
do BIT[p]++;
while (p -= p & -p);
}
void dec(int p) { /// decrease the amount of visited
do BIT[p]--;
while (p -= p & -p);
}
int getValue(int p) { /// count number of inversion pairs
int res = 0;
do res += BIT[p];
while ((p += p & -p) < BIT.size());
return res;
}
int main()
{
int n, m;
cin >> n >> m;
BIT.assign(n + 1, 0);
vector<int> perm(n + 1, 0);
vector<int> calc(n + 1, 0);
for (int i = 1; i <= n; ++i)
{
perm[i] = i; /// assigning value
calc[i] = calc[i - 1] + getValue(perm[i]); /// dp-precalculating
inc(perm[i]); /// update value
}
int res = 0;
res += (calc[n] == m);
/// Iterating over all possible permutation
for (vector<int> n_perm(perm); next_permutation(1 + all(n_perm)); next_permutation(1 + all(perm)))
{
int p = 1; /// position of first different between two consecutive permutations (perm, n_perm)
for (int l = 1, r = n; l <= r; )
{
int m = (l + r) / 2; /// middle point
if (perm[m] == n_perm[m] && perm[m - 1] == n_perm[m - 1]) /// this position is valid
{
p = m;
l = m + 1;
}
else r = m - 1;
}
for (int i = p; i <= n; ++i) dec(perm[i]); /// reset the tree before update this path [p..n]
for (int i = p; i <= n; ++i)
{
calc[i] = calc[i - 1] + getValue(n_perm[i]); /// re-calculating the different path
inc(n_perm[i]); /// update new value
}
res += (calc[n] == m); /// increase the counter when it is valid
}
cout << res;
return 0;
}
Using formula to improve furthur more
The formula is coefficients in expansion of $$$\underset{i \in [0, n)}{\prod}(1+x+...+x^i)$$$
Lets $$$f[n][k]$$$ be the number of $$$nth$$$ permutation with $$$k$$$ inversion pairs
We have $$$f[n][0] = 1$$$ (since there is only one permutation $$$[1..n]$$$ have $$$0$$$ inversion pairs)
We have $$$f[0][k] = 0$$$ (since there is no elements so there is no inversion pairs)
Becareful with $$$f[0][0] = 1$$$ (since there is no elements there is exactly zero amount of inversion pairs)
Maximum Possible Valid $$$max_k$$$ is $$$\frac{n \times (n + 1)}{2} - 1$$$ (strictly decreasing permutation $$$[n..1]$$$)
Minumum Possible Valid $$$min_k$$$ is $$$0$$$ (strictly increasing permutation $$$[1..n]$$$)
If $$$k$$$ is out of range $$$(k < min_k) or (k > max_k)$$$ then $$$f[n][k] = 0$$$
The total number of possible valid $$$k \in [min_k, max_k]$$$ is $$$total = max_k - min_k + 1 = \frac{n \times (n + 1)}{2}$$$
We have $$$f[n][k] = f[n][total - k]$$$ (since the number of $$$nth$$$ permutations within $$$k$$$ inversion pairs is the same as the number of $$$nth$$$ permutations without $$$k$$$ inversion pairs)
From sequences of permutations $$$f[n]$$$ with all possible $$$k$$$ we can find the sequence $$$f[n + 1]$$$ (you can read here)
We have the formula $$$f[n][k] = sum(f[n - 1][k - 1 \rightarrow k - n])$$$
- Lets $$$f[n][k]$$$ be the number of $$$nth$$$ permutation with no more than $$$k$$$ inversion pairs
By this way, we can calculate $$$f[n][k]$$$ in $$$O(1)$$$ from $$$f[n][k - 1]$$$ and $$$f[n - 1][0..k]$$$
- We can ignore sequences of permutations $$$f[n - 2] \rightarrow f[0]$$$ when it is calculate
By this way, we can calculate $$$f[n][k]$$$ in $$$O(k)$$$ space
vector<vector<int> > f;
int solve(int n, int k)
{
int total = n * (n - 1) / 2; /// number of possible k
if (k < 0 || k > total) return 0; /// k is out of range
minimize(k, total - k); /// f[n][k] = f[n][total - k]
if (f[n][k] != -1) return f[n][k]; /// if f[n][k] is calculated
if (k == 0) return f[n][0] = 1; /// strictly increasing permutation
if (n == 0) return f[0][k] = 0; /// empty permutation
return f[n][k] = (solve(n, k - 1) + solve(n - 1, k) - solve(n - 1, k - n) + MOD) % MOD;
}
int main()
{
int n, k;
cin >> n >> k;
int total = n * (n - 1) / 2;
if (k < 0 || k > total) /// k is out of range
{
cout << 0;
return 0;
}
minimize(k, total - k); /// f[n][k] = f[n][total - k]
f.assign(n + 1, vector<int>(k + 1, -1)); /// init dp-table
cout << solve(n, k);
return 0;
}
int main()
{
int n, k;
cin >> n >> k;
int total = n * (n - 1) / 2;
if (k < 0 || k > total) /// k is out of range
{
cout << 0;
return 0;
}
minimize(k, total - k);
int f[n + 1][k + 1];
f[0][0] = 1; /// base case f[n][0] = 1
for (int i = 1; i <= n; ++i) f[0][i] = 0; /// base case f[0][k] = 0
for (int i = 1; i <= n; ++i)
{
bool cur = i & 1; /// current
bool pre = !cur; /// previous
f[cur][0] = 1; /// base case f[n][0] = 1
for (int j = 1; j <= k; ++j)
{
f[cur][j] = (f[cur][j - 1] + f[pre][j]) % MOD;
if (j >= i)
f[cur][j] = (f[cur][j] - f[pre][j - i] + MOD) % MOD;
}
}
cout << f[n & 1][k];
return 0;
}
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 ?"
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: .
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
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 ?
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.
is there an simpler explanation. I am getting confused by mathematical equations
Yes, by checking AC codes on CC long ongoing contest
Just say that you want a solution for the ongoing CC Long Challenge
He asked that 3 months ago.
I see, sorry for author.