TieForMax
TCO19 SRM 747 · 2019-01-09 · by misof
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?
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.
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}.
50 50 Returns: 0.49549217175140714
Submissions are judged against all 74 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TieForMax with a public method double getProbability(int t, int p) · 74 test cases · 2 s / 256 MB per case