RandomSelection | Topcoder Archive

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)

Definition

Class:: RandomSelection
Method:: expectedMaximum
Parameters:: int, int, int, int, int[]
Returns:: double
Method signature:: double expectedMaximum(int n, int T, int seed, int Amod, int[] Aprefix)
(be sure your method is public)

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.

Examples

```
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}.

528274614

574635344

{0}

Returns: 1.0994012979929392E9

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.