RandomPartition | Topcoder Archive

Problem Statement

Oh, Ramanujan found the previous problem too easy. Along with partitions, he also likes probability. So lets mix them.

He wants to build 2*N buildings. Their heights are given in the int[] H.

The buildings have to be partitioned into two rows: row A and row B. We will use A[i] to denote the height of the i-th building (0-based index) in row A, and B[i] for row B. The partition into A and B must satisfy the following constraints:

Each row must contain N buildings.
The rows must be aligned: for each i, the i-th building in row A will stand opposite to the i-th building in row B.
The heights of buildings in row A must form a non-decreasing sequence: for each i, A[i] <= A[i+1].
The heights of buildings in row B must form a non-increasing sequence: for each i, B[i] >= B[i+1].

The instability of a pair of buildings that stand opposite each other is the absolute difference between their heights: |A[i] - B[i]|.

The instability of the whole partition is the average instability of all N such pairs of buildings.

But, oh. We don't know the partition Ramanujan will use. All we know is, the buildings will be partitioned into A and B uniformly at random. (Each of the 2N choose N possibilities is equally likely, i.e., different buildings of the same height are considered to be different.) Once the partition into A and B is fixed, the sequence of building heights in each row is uniquely determined by constraints 3 and 4.

You have to return the expected value of the instability of the chosen partition.

It can be shown that the expected value can be expressed as a reduced fraction P / Q, where Q isn't a multiple of 786433. Return (P * inverse(Q)) modulo 786433.

We provide nums[], N, M, B1, and B2. Since the system does not support large input sizes, use the generator shown below to construct the array H of size 2*N.

H = integer array of size 2N
for(int i = 0; i &lt; nums.size(); i++) {
	H[i] = nums[i];
}
for(int i = nums.size(); i &lt; 2 * N; i++) {
	H[i] = (H[i - 1] * B1 + H[i - 2] * B2) % M; // take care of overflows.
}

Definition

Class:: RandomPartition
Method:: expectedSum
Parameters:: int[], int, int, int, int
Returns:: int
Method signature:: int expectedSum(int[] nums, int N, int M, int B1, int B2)
(be sure your method is public)

Notes

The reference solution does not depend on any properties of the generator used to produce H.
By inverse(Q) we mean the inverse element to Q modulo 786433. That is, (Q * inverse(Q)) mod 786433 = 1.

Constraints

N will be between 1 and 50,000, inclusive.
M will be between 2 and 100,000, inclusive.
B1 and B2 will be between 0 and M-1, inclusive.
nums will have between 2 and min(2*N, 500) elements, inclusive.
Each element of nums will be between 0 and M-1, inclusive.

Examples

```
{1,2}
```
```
1
```
```
14
```
```
13
```
```
13
```
```
Returns: 1
```
There are two possible partitions. A = {1} B = {2} A = {2} B = {1} Instability for both partitions is 1.

{17,29,1,2,1,10,9,1729}

Returns: 593461

H = {17,29,1,2,1,10,9,1729}

```
{1,7,2,9}
```
```
10
```
```
1729
```
```
17
```
```
29
```
```
Returns: 315441
```
Heights of the 2*N buildings: H = {1,7,2,9,211,390,646,1544,28,298,691,1370,104,2,1321,38,917,1130,849,520}

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.