PERMUT1 - Permutations
Let A = [a1,a2,...,an] be a permutation of integers 1,2,...,n. A pair of indices (i,j), 1<=i<=j<=n, is an inversion of the permutation A if ai>aj. We are given integers n>0 and k>=0. What is the number of n-element permutations containing exactly k inversions?
For instance, the number of 4-element permutations with exactly 1 inversion equals 3.
Write a program which for each data set from a sequence of several data sets:
- reads integers n and k from input,
- computes the number of n-element permutations with exactly k inversions,
- writes the result to output.
The first line of the input file contains one integer d, 1<=d<=10, which is the number of data sets. The data sets follow. Each data set occupies one line of the input file and contains two integers n (1<=n<=12) and k (0<=k<=98) separated by a single space.
The i-th line of the output file should contain one integer - the number of n-element permutations with exactly k inversions.
Sample input: 1 4 1 Sample output: 3
one of the best problem i ever had on dp...
func(n,k)=summation func(n-1,k-i)...........and then AC:)
You can solve it using bitmask DP.
A good question. Feel free to think as you wish. Dont stick to whats mentioned in the comments! :-)
can be solved without dp also !
Very nice question!!
I did simple recursion without DP and it didn't TLE! Very un-strict TL :/
OK, I've been writing cases and doing the permutations by hand to prove my algorithm. It works fine according to my understanding of the problem, but maybe that's what's wrong, maybe I just don't get the problem. For n = 7, k = 2, answer = 10? n = 7, k = 3, answer = 4? n = 8, k = 3, answer = 10? Any difficult/special test cases I'm missing maybe? When k = 0, answer = 1? when k > n (can that be a test case?) answer = 0? I don't need help with the algorithm, just with properly understanding the problem. Thanks.
Try with bitmasking :p