NestedRandomness | Topcoder Archive

Problem Statement

Consider a function randomInt(integer N) that takes an integer N and returns an integer uniformly at random in the range 0 to N-1. If that function is nested, as in randomInt(randomInt(N)), the probability distribution changes, and some numbers are more likely than others. Given an int nestings defining the number of times the function is nested (1 indicates randomInt(N), 2 indicates randomInt(randomInt(N)), and so on), an int N and an int target, return the probability that the result of nestings nested calls to randomInt with the parameter N will result in target.

Definition

Class:: NestedRandomness
Method:: probability
Parameters:: int, int, int
Returns:: double
Method signature:: double probability(int N, int nestings, int target)
(be sure your method is public)

Notes

Calling randomInt(0) causes an error to occur, and hence can never cause an outcome of target.
Your return must have a relative or absolute error less than 1E-9.

Constraints

N will be between 1 and 1000, inclusive.
nestings will be between 1 and 10, inclusive.
target will be between 0 and N-nestings, inclusive.

Examples

```
5
```
```
2
```
```
1
```
```
Returns: 0.21666666666666667
```
There are 3 ways of ending up with a 1 after calling randomInt(randomInt(5)). The inner call can result in a 4, 3, or a 2. Each of these possibilities occurs with a probability of 1/5. The probabilities of achieving a 1 with each of those results are 1/4, 1/3, and 1/2, respectively. This gives us a final probability of (1/5)*(1/4+1/3+1/2) = 13/60.
```
10
```
```
4
```
```
0
```
```
Returns: 0.19942680776014104
```

Returns: 1.0461776397050886E-30

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.