MedianSegments | Topcoder Archive

Problem Statement

The median of an array with an odd number of elements is the element that would be in the middle if we sorted the array. For example, the array {10, 40, 50, 20, 30} has the median 30.

Given is an array A[0..N-1] of non-negative integers. Also given is an index K into the array such that the value A[K] has no other occurrence in the array A.

Count all contiguous subarrays of A such that their length is odd and their median is A[K].

In order to keep the input size small, the array A is pseudorandom and should be generated as follows:


L = length(Aprefix)
for i = 0 to L-1:
    A[i] = Aprefix[i]

state = Aprefix[L-1]
for i = L to N-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    A[i] = state modulo M

Definition

Class:: MedianSegments
Method:: count
Parameters:: int, int, int[], int
Returns:: long
Method signature:: long count(int N, int K, int[] Aprefix, int M)
(be sure your method is public)

Notes

The reference solution does not depend on the input being pseudorandom, it would solve the problem for any array of the given length.

Constraints

N will be between 1 and 300,000, inclusive.
K will be between 0 and N-1, inclusive.
Aprefix will have between 1 and min(100, N) elements, inclusive.
M will be between 1 and 1,000,000,007, inclusive.
Each element of Aprefix will be between 0 and M-1, inclusive.
The value A[K] will have no other occurrence in A.

Examples

```
10
```
```
3
```
```
{30, 40, 50, 60, 70, 80, 90, 100, 110, 120}
```
```
12345
```
```
Returns: 4
```
The whole array A is given. A[3] is 60. There are four subarrays of A with the median 60: {60}, {50, 60, 70}, {40, 50, 60, 70, 80}, and {30, 40, 50, 60, 70, 80, 90}.
```
9
```
```
4
```
```
{0, 10, 2, 9, 5, 4, 6, 7, 3}
```
```
47
```
```
Returns: 11
```
The entire array A is one of the possibilities.
```
13
```
```
5
```
```
{47023}
```
```
12345678
```
```
Returns: 5
```
The generated array should look as follows: A = { 47023, 11719828, 11657315, 11330458, 6137953, 2037036, 5878707, 33880, 4844967, 1163070, 1778073, 8789540, 2243117 }.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.