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.

Input

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.

Output

The i-th line of the output file should contain one integer - the number of n-element permutations with exactly k inversions.

Example

Sample input:
1
4 1

Sample output:
3

 < Previous 1 2 3 4 Next > whyamievenhere: 2018-12-20 16:00:30 just ensure dp==1 .. got 2 WA because of it.. salman3007: 2018-10-26 20:18:35 one of the best problem i ever had on dp... be1035016: 2018-06-28 15:32:34 good problem:) nice and elegant dp solution sherlock11: 2018-05-30 20:26:29 func(n,k)=summation func(n-1,k-i)...........and then AC:) vsr625: 2018-02-11 05:26:27 You can solve it using bitmask DP. rohit1507: 2017-09-16 13:49:46 A good question. Feel free to think as you wish. Dont stick to whats mentioned in the comments! :-) t_s_vedha29: 2017-03-26 19:32:12 can be solved without dp also ! for each i in [1,n-1], let S(i) = number of inversions contributed by ith element (a[i] > a[j] && i < j) in all possible permutations. S(i) always has the range : [0,n-i] so the problem changes to : finding number solution for the following equation, S(1) + S(2) ......... + S(n-1) = k, with given constraints we can solve this without TLE (think about this!!) ,give it a try :) rishi_07: 2017-03-16 11:55:56 Very nice question!! coderaashir: 2017-02-11 10:31:58 I did simple recursion without DP and it didn't TLE! Very un-strict TL :/ taiken: 2017-02-01 16:13:16 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.