Connection Status:
Competition Arena > UpDownNess

UpDownNess

2016 TCC India Online Round · 2016-03-24 · by IH19980412

2016 TCC India Online Round · 2016-03-24 · by IH19980412 · Dynamic Programming
Class Name: UpDownNess
Return Type: int
Method Name: count
Arg Types: (int, int)
Problem Statement

Problem Statement

Given a permutation P, a lo-hi-lo triple is any triple (i,j,k) of valid indices into P such that i < j < k and P[i] < P[j] > P[k]. Note that there is no requirement on the comparison between P[i] and P[k].

You are given the ints N and K. Among all N! permutations of the numbers 1 through N, consider those that contain exactly K lo-hi-lo triples. Let X be the number of such permutations. Compute and return the value (X modulo 1,000,000,007).

Constraints

  • N is between 1 and 50, inclusive.
  • K is between 0 and 5000, inclusive.
Examples
0)
3
1
Returns: 2

{1,3,2} and {2,3,1} meet the condition.

1)
3
0
Returns: 4

{1,2,3},{2,1,3},{3,1,2} and {3,2,1} meet the conditon.

2)
4
3
Returns: 4

Here, the four good permutations are {1,3,4,2}, {1,4,3,2}, {2,3,4,1}, and {2,4,3,1}. For the permutation P={1,3,4,2} the three lo-hi-lo triples of indices are the following ones: (0,1,3), because we have 1 < 3 > 2. (0,2,3), because we have 1 < 4 > 2. (1,2,3), because we have 3 < 4 > 2. (Note that all the indices used above are 0-based: P[0]=1, P[1]=3, P[2]=4, and P[3]=2.)

3)
19
19
Returns: 24969216
4)
50
2000
Returns: 116596757

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

Coding Area

Language: C++17 · define a public class UpDownNess with a public method int count(int N, int K) · 84 test cases · 2 s / 256 MB per case

Submitting as anonymous