PERMUT1 - Permutations editorial -spoj - UCS - Unleash-Coding-Skills

Wednesday, 28 March 2018

PERMUT1 - Permutations editorial -spoj - UCS

<h2 class="text-center" id="problem-name"> PERMUT1 - Permutations</h2>

 

This is question for  PERMUT1 - Permutations editorial - spoj

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.

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 1 

Sample output:

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 ai>aj

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