PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
It seems paradoxical that if 99 chefs start with 1 token each, it’s just as likely that in the final cook-off one chef will have 98 tokens and the other will have 1 as it is that one will have 49 and the other 50. In fact, if we ask the question “How many different chefs’ tokens will be held by one of the finalists?”, each number from 1 to C-1 is equally likely. We can therefore solve the task as follows:
Denote by N the total number of tokens. For each number i between 1 and C-1, and each number j between 1 and N, compute the number of ways to choose i chefs whose total number of tokens is j. Divide this number by the number of ways to choose i chefs from C chefs (a binomial coefficient) in order to get the probability that a finalist has j tokens, given that their tokens come from i chefs. Then divide by C-1 to get the probability of a finalist having j tokens from i chefs. Since we’re computing an expected value, we multiply by the token difference abs(j-(N-j)) and sum over all i,j pairs. This computation can be done using dynamic programming on a 2-dimensional array.
SETTER’S SOLUTION
Can be found here.
TSTER’S SOLUTION
Can be found here.