This is question for PERMUT1 - Permutations editorial - spoj

Let A = [a

For instance, the number of 4-element permutations with exactly 1 inversion equals 3.

_{1},a_{2},...,a_{n}] 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 a_{i}>a_{j}. 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.

### Task

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 1Sample output:3

#### Problem Link for PERMUT1 - Permutations is:

#### http://www.spoj.com/problems/PERMUT1/

The solution for PERMUT1 - Permutations is explained from here.

Let us see the code or solution to PERMUT1 - Permutations first.

#include <iostream> using namespace std; long long dp[15][100]; long long count(long long n,long long k) {// Solution to PERMUT1 - Permutations if(n==0) return 0; if(k==0) return 1; if(dp[n][k]!=-1) return dp[n][k]; long long val=0; for(int i=0;i<n&&k-i>=0;i++) { val+=count(n-1,k-i); } return (dp[n][k]=val); } int main() {//Main method starts for PERMUT1 - Permutations problem

long long t,i,j,k,n;

cin>>t;

for(i=0;i<t;i++)

{//First take input here dp is used.

cin>>n>>k;

for(int l=0;l<=n;l++)

{

for(int m=0;m<=k;m++)

{

dp[l][m]=-1;

}

}

cout<< count(n,k)<<endl;

}

return 0;

}

What is inversion permutation in problem PERMUT1 - Permutations is that

suppose consider any pair of indices (i,j), 1<=i<=j<=n, is an

*inversion*of the permutation A if a_{i}>a_{j}.
According to problem PERMUT1 - Permutations if n equals to zero then there are 0 inversions of permutations are possible.

In
the same way, According to problem PERMUT1 - Permutations if k equals
to zero then number of inversion of permutations is one.This is simply
the permutation is in ascending order.

These two are base cases in problem PERMUT1 - Permutations problem solution.

The other DP approach is used is implemented in the code and the final value or answer of our problem is present in dp[n][k].

This is solution to the problem PERMUT1 - Permutations.

Happy Coding.........

Feel free to ask queries in comments...........

## No comments:

## Post a Comment