TieForMax | Topcoder Archive

Problem Statement

I have t tokens and p initially empty piles. One after another, I place each token onto a pile chosen uniformly at random. (All choices are mutually independent.)

What is the probability that once I'm done, multiple piles will be tied for being the largest?

Definition

Class:: TieForMax
Method:: getProbability
Parameters:: int, int
Returns:: double
Method signature:: double getProbability(int t, int p)
(be sure your method is public)

Notes

Your return value must have an absolute error at most 1e-9.

Constraints

t will be between 1 and 50, inclusive.
p will be between 1 and 50, inclusive.

Examples

```
7
```
```
1
```
```
Returns: 0.0
```
I will make a single pile with seven tokens. With just one pile there can be no ties.
```
2
```
```
2
```
```
Returns: 0.5
```
With probability 50% I will get a unique largest pile with two tokens, and with probability 50% I will get a tie: two piles with one token each.
```
3
```
```
3
```
```
Returns: 0.2222222222222222
```
The tie can only happen if I get three piles with one token on each of them. The probability of that event is 6/27 = 2/9.
```
6
```
```
4
```
```
Returns: 0.380859375
```
Now there are multiple configurations in which the maximum isn't unique. For example, the pile sizes can be {1,2,1,2}, {0,3,3,0}, or even {0,2,2,2}.

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.