### PROBLEM LINK:

**Author:** Istvan Nagy

**Tester:** Suhash Venkatesh and Kevin Atienza

**Editorialist:** Kevin Atienza

### PREREQUISITES:

Probability, dynamic programming

### PROBLEM:

There are N righties and M lefties in a single-elimination tournament (N+M is a power of two). The probability of a lefty winning against a righty is p. What is the probability that a lefty wins the whole tournament, assuming all tournaments are equally likely?

### QUICK EXPLANATION:

The problem can be solved with dynamic programming. Let F_p(n,m) be the probability that a lefty wins in a tournament with 2^n people and m lefties, assuming a lefty wins against a righty with probability p (the answer is F_p(\log_2(N+M), M)). Then we have the base cases F_p(n,0) = 0 and F_p(n,2^n) = 1.

Now, let’s try to compute F_p(n,m) for a general (n,m) pair. How many tournaments are there such that there are exactly c lefties in the “left” tournament? It can be shown to be exactly {m \choose c}{2^n - m \choose 2^{n-1} - c}. Let’s denote this quantity by T_c. Assuming there are c lefties in the left tournament, then:

- The probability that a lefty wins the left tournament is F_p(n-1,c). Let’s denote this quantity by p_L.
- The probability that a lefty wins the right tournament is F_p(n-1,m-c). Let’s denote this quantity by p_R.
- The probability that a lefty wins the overall tournament is p_Lp_R + (1 - p_L)p_R\cdot p + p_L(1 - p_R)\cdot p.

Therefore, the overall probability is the weighted average of all such probabilities, weighted by T_c, i.e.:

For a fixed (n,m) pair, the sum can be computed in O(m) = O(2^n) time (assuming binomial coefficients are precomputed). Therefore, the overall number of steps is proportional to:

### EXPLANATION:

We are given that N+M is a power of two, so if we let 2^n = N+M, then every player needs to win exactly n matches to win the whole tournament. Let F_p(n,m) be the probability that a lefty wins in a tournament with 2^n people and m lefties, assuming a lefty wins against a righty with probability p (so that the answer is F_p(n, M)). Then we have the base cases F_p(n,0) = 0 (this is the case where there are no lefties) and F_p(n,2^n) = 1 (this is the case where all players are lefties).

Now, the 2^n-player tournament itself consists of two 2^{n-1}-player subtournaments, plus a final round among the winners of the subtournaments to determine the overall winner. Let’s say that the two subtournaments have already finished and we have now two finalists:

- If both finalists are lefties, then the probability of this lefty winning the final round is exactly 1.
- If exactly one finalist is a lefty, then the probability of this lefty winning the final round is exactly p, by definition.
- If none of the finalists are lefties, then the probability of this lefty winning the final round is exactly 0.

Unfortunately, it’s not guaranteed that exactly one of the finalists is a lefty. But if we assume that there are c lefties in the left tournament, then we know that (by definition):

- The probability that a lefty wins the left tournament is F_p(n-1,c).
- The probability that a lefty wins the right tournament is F_p(n-1,m-c).

Now, if we let p_L = F_p(n-1,c) and p_R = F_p(n-1,m-c), then:

- The probability that the two finalists are lefties is p_Lp_R,
- The probability that exactly one of the finalists is a lefty is p_L(1-p_R) + (1-p_L)p_R,
- The probability that none of the finalists are lefties is (1-p_L)(1-p_R).

Taking all of the possibilities into account, the probability that a lefty wins the overall tournament is:

or simply

But this is assuming there are exactly c lefties in the left tournament. To compute F_p(n,m) overall, we must take all these possibilities into account. Specifically, let f_c be the probability that there are exactly c lefties in the left tournament. Then:

where p_L = F_p(n-1,c) and p_R = F_p(n-1,m-c).

But what is f_c? Since all tournaments are equally likely, this probability is proportional to the number of tournaments in which there are c lefties in the left tournament. Therefore, if T_c is the number of tournaments where there are exactly c lefties in the left tournament, then we have:

Finally, we still have to discuss how to compute T_c. In this case, a simple counting argument works: Since there are m lefties overall and we need to have c lefties in the left tournament, we need to choose these c lefties from our pool of m lefties and we need to choose 2^{n-1} - c righties from our pool of 2^n - m righties. Therefore, we have the following:

Combining all the above, we now have a recurrence of F_p(n-1,c). To compute the answer F_p(\log_2 (N+M),M), we must compute all F_p(n,m) for 0 \le n \le \log_2 (N+M) and 0 \le m \le M. Remember that each F_p(n,m) can be computed in O(2^n) time (assuming all the needed F_p's have already been calculated). Therefore, the total running time is:

Therefore, the algorithm runs in O((N+M)M) time

### Time Complexity:

O\left((N+M)^2\right) or O\left((N+M)M\right)

### AUTHOR’S AND TESTER’S SOLUTIONS:

To be uploaded soon.