LittleElephantAndPermutationDiv1

SRM 592 · 2013-06-25 · by Witaliy

SRM 592 · 2013-06-25 · by Witaliy · Brute Force, Dynamic Programming

Show categories

Class Name: LittleElephantAndPermutationDiv1

Return Type: int

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. Let X be 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.) Return the value (X modulo 1,000,000,007).

Constraints

N will be between 1 and 50, inclusive.
K will be between 1 and 2500, 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

10
74
Returns: 484682624

50
1000
Returns: 539792695

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 LittleElephantAndPermutationDiv1 with a public method int getNumber(int N, int K) · 57 test cases · 2 s / 256 MB per case