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
Definition
- Class:
- UpDownNess
- Method:
- count
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int count(int N, int K)
- (be sure your method is public)
Constraints
- N is between 1 and 50, inclusive.
- K is between 0 and 5000, inclusive.
Examples
3
1
Returns: 2
{1,3,2} and {2,3,1} meet the condition.
3
0
Returns: 4
{1,2,3},{2,1,3},{3,1,2} and {3,2,1} meet the conditon.
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.)
19
19
Returns: 24969216
50
2000
Returns: 116596757
13
4831
Returns: 0
38
1100
Returns: 577779367
4
2863
Returns: 0
41
2542
Returns: 214583147
25
2069
Returns: 0
38
3608
Returns: 211620140
10
4212
Returns: 0
27
2385
Returns: 0
43
1010
Returns: 549686354
43
3125
Returns: 822857731
9
1810
Returns: 0
47
3712
Returns: 880842464
18
561
Returns: 0
4
2151
Returns: 0
16
1388
Returns: 0
15
1711
Returns: 0
25
4601
Returns: 0
11
3479
Returns: 0
11
2987
Returns: 0
40
380
Returns: 694672814
13
2901
Returns: 0
48
3031
Returns: 795625621
41
244
Returns: 145104109
29
4990
Returns: 0
13
3359
Returns: 0
10
983
Returns: 0
38
1393
Returns: 169670558
33
3254
Returns: 0
49
1649
Returns: 819733389
26
870
Returns: 23740215
30
1545
Returns: 964628922
18
2189
Returns: 0
37
3531
Returns: 227096736
43
4639
Returns: 626525840
7
275
Returns: 0
9
2087
Returns: 0
30
753
Returns: 1897098
10
3000
Returns: 0
20
1917
Returns: 0
18
2772
Returns: 0
49
448
Returns: 770785544
3
3219
Returns: 0
48
832
Returns: 552996047
45
4964
Returns: 975031313
14
484
Returns: 0
49
3640
Returns: 100698857
48
3658
Returns: 474994210
36
2782
Returns: 877257939
44
3556
Returns: 224923586
41
2952
Returns: 502919082
29
2547
Returns: 0
5
4567
Returns: 0
4
3677
Returns: 0
11
4266
Returns: 0
24
3988
Returns: 0
25
3707
Returns: 0
19
3257
Returns: 0
35
4010
Returns: 0
34
2225
Returns: 145392456
41
874
Returns: 370620721
50
4363
Returns: 116796144
50
3775
Returns: 449507589
50
2063
Returns: 334642230
50
1930
Returns: 602668627
50
4907
Returns: 466964758
50
2247
Returns: 487060266
50
2524
Returns: 750120766
50
2189
Returns: 741206087
50
3166
Returns: 124127329
50
607
Returns: 799665847
50
4930
Returns: 75652705
50
4987
Returns: 204070809
50
4915
Returns: 980030145
2
0
Returns: 2
1
0
Returns: 1
50
5000
Returns: 118074500
50
10
Returns: 393767951
50
1342
Returns: 165141112
30
20
Returns: 565359673