RandomPartition
SRM 781 · 2020-03-19 · by sinus_070
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
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 < nums.size(); i++) {
H[i] = nums[i];
}
for(int i = nums.size(); i < 2 * N; i++) {
H[i] = (H[i - 1] * B1 + H[i - 2] * B2) % M; // take care of overflows.
}
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.
{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}
8
9271
9
10
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}
{1,2,3,4,5,6}
50000
99991
3
1
Returns: 436297
{0,0,0,0,0,0}
50000
14
13
13
Returns: 0
{1, 1, 1, 1, 7, 1}
6
100
0
0
Returns: 2
Regardless of which three of these six buildings are chosen to be in row A, there will always be two (1, 1) pairs and a (1, 7) pair, so the instability of the partition will be (0 + 0 + 6) / 3 = 2.
Submissions are judged against all 63 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RandomPartition with a public method int expectedSum(vector<int> nums, int N, int M, int B1, int B2) · 63 test cases · 2 s / 256 MB per case