TENNIS - Editorial

[kevinsogo]

PROBLEM LINK:

Contest

Practice

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.:

F_p(n,m) = \frac{\sum_c T_c\cdot( p_Lp_R + (1 - p_L)p_R\cdot p + p_L(1 - p_R)\cdot p )}{\sum_c T_c}

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:

\sum_{2^n \le N+M} \sum_{0 \le m \le 2^n} 2^n = \sum_{2^n \le N+M} O(4^n) = O\left(4^{\log_2 (N+M)}\right) = O\left((N+M)^2\right)

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:

p_Lp_R\cdot 1 + [p_L(1-p_R) + (1-p_L)p_R]\cdot p + (1-p_L)(1-p_R)\cdot 0

or simply

p_Lp_R + [p_L(1-p_R) + (1-p_L)p_R]\cdot p

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:

F_p(n,m) = \sum_{c=0}^{2^n} f_c \cdot [p_Lp_R + [p_L(1-p_R) + (1-p_L)p_R]\cdot p]

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:

f_c = \frac{T_c}{\sum_{k=0}^{2^n} T_k}

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:

T_c = {m \choose c}{2^n - m \choose 2^{n-1} - c}

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:

\begin{aligned} \sum_{n=0}^{\log_2 (N+M)} \sum_{m=0}^M O(2^n) &= \sum_{n=0}^{\log_2 (N+M)} O(2^n M) \\\ &= O((2^{n+1}-1) M) \\\ &= O(2^n M) \\\ &= O((N+M) M) \end{aligned}

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.

[ironmandhruv]

@kevinsogo your editorials are always great!

[kevinsogo]

@ironmandhruv thanks! I really appreciate the feedback

[faceless_man]

@kevinsogo This is a very good editorial. learned a lot. thanks