RandomSelection
SRM 770 · 2019-10-31 · by jy_25
Problem Statement
Consider an integer array A of size n . For each i from 0 to n - 1, inclusive, you choose a real number a[i] uniformly at random from the range [0, A[i]]. Find the expected value of maximum of all a[i].
In order to keep the input small, you are given integers T, seed, Amod and an integer array Aprefix . Use the following pseudocode to generate A:
for i = 0 .. len(Aprefix)-1:
A[i] = Aprefix[i]
state = seed
for i = len(Aprefix) .. n-1:
state = (1103515245 * state + 12345) modulo 2^31
A[i] = T + (state modulo Amod)
Notes
- Note that the values a[i] are real, not just integer.
- Your answer is considered correct if its absolute or relative error doesn't exceed 10 -9 .
Constraints
- Aprefix will contain between 1 and 100 integers, inclusive.
- n will be between len(Aprefix) and 10^5, inclusive.
- T will be between 0 and 10^9, inclusive
- seed will be between 0 and 2^31 - 1, inclusive.
- Amod will be between 1 and 10^9, inclusive.
- Each element of Aprefix will be between 0 and 2 * 10^9, inclusive.
2
0
0
1000000000
{2, 2}
Returns: 1.3333333333333335
A = {2, 2}. The expected value of the maximum of k real numbers, each randomly chosen in the same range [0, L] is kL/(k+1). The answer is therefore 4/3.
3
1
2
10
{2}
Returns: 4.215277777777778
A = {2, 8, 3}.
100000
528274614
192837
574635344
{0}
Returns: 1.0994012979929392E9
64495
335479466
153927989
636096486
{611523063, 241187991, 475005940, 630901156, 66479698, 166182240, 164037007, 545915628, 342196526, 402812460, 439411845, 142896520, 268266684, 228786455, 483254904, 167696554, 134976857, 25304188, 86600607, 191264021, 275124228, 312075183, 212731094, 27281415, 427427919, 180698454, 104420849, 411818418, 15589814, 583838496, 316346436, 525195953, 472187713, 129727472, 540629217, 92526406, 267757789, 210232195, 401494922, 524387170, 566381810, 265278262, 225997695, 222850070, 272102103, 562444664, 364278654, 164472669, 588726353, 616401566, 274647416, 618057085, 290844644, 231204110, 79525096}
Returns: 9.673800035928203E8
728
411249573
457703492
28479276
{16406810, 12201065, 20778999, 2616820, 4694225, 8350781, 26779592, 4637826, 24581707, 24925374, 24148241, 22724663, 27885741, 19335314, 9454552, 9133230, 12325533, 28458984, 17052474, 12312560}
Returns: 4.3468326588264245E8
Submissions are judged against all 170 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RandomSelection with a public method double expectedMaximum(int n, int T, int seed, int Amod, vector<int> Aprefix) · 170 test cases · 2 s / 256 MB per case