LittleElephantAndPermutationDiv2

SRM 592 · 2013-06-25 · by Witaliy

SRM 592 · 2013-06-25 · by Witaliy · Brute Force

Show categories

Class Name: LittleElephantAndPermutationDiv2

Return Type: long

Method Name: getNumber

Arg Types: (int, int)

Problem Statement

This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.

Little Elephant from the Zoo of Lviv likes permutations. A permutation of size N is a sequence (a₁, ..., a_N) that contains each of the numbers from 1 to N exactly once. For example, (3,1,4,5,2) is a permutation of size 5.

Given two permutations A = (a₁, ..., a_N) and B = (b₁, ..., b_N), the value magic(A,B) is defined as follows: magic(A,B) = max(a₁,b₁) + max(a₂,b₂) + ... + max(a_N,b_N).

You are given the int N. You are also given another int K. Return the number of pairs (A,B) such that both A and B are permutations of size N, and magic(A,B) is greater than or equal to K. (Note that A and B are not required to be distinct.)

Constraints

N will be between 1 and 10, inclusive.
K will be between 1 and 100, inclusive.

Examples

1
1
Returns: 1

For N=1 the only pair of permutations is ( (1), (1) ). The magic of this pair of permutations is 1, so we count it.

2
1
Returns: 4

Now there are four possible pairs of permutations. They are shown below, along with their magic value. magic( (1,2), (1,2) ) = 1+2 = 3 magic( (1,2), (2,1) ) = 2+2 = 4 magic( (2,1), (1,2) ) = 2+2 = 4 magic( (2,1), (2,1) ) = 2+1 = 3 In all four cases the magic value is greater than or equal to K.

3
8
Returns: 18

When A = (1,2,3), there are 3 possibilities for B: (2,3,1), (3,1,2) and (3,2,1). For each of the other 5 values of A, it can be shown that there are 3 possibilities for B as well. Therefore the answer is 3*6 = 18.

10
47
Returns: 13168189440000

7
1
Returns: 25401600

Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LittleElephantAndPermutationDiv2 with a public method long long getNumber(int N, int K) · 57 test cases · 2 s / 256 MB per case