PROBLEM LINK:Author: Istvan Nagy PREREQUISITES:Probability, dynamic programming PROBLEM:There are $N$ righties and $M$ lefties in a singleelimination 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^{n1}  c}$. Let's denote this quantity by $T_c$. Assuming there are $c$ lefties in the left tournament, then:
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^{n1}$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:
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):
Now, if we let $p_L = F_p(n1,c)$ and $p_R = F_p(n1,mc)$, then:
Taking all of the possibilities into account, the probability that a lefty wins the overall tournament is: $$p_Lp_R\cdot 1 + [p_L(1p_R) + (1p_L)p_R]\cdot p + (1p_L)(1p_R)\cdot 0$$ or simply $$p_Lp_R + [p_L(1p_R) + (1p_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(1p_R) + (1p_L)p_R]\cdot p]$$ where $p_L = F_p(n1,c)$ and $p_R = F_p(n1,mc)$. 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^{n1}  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^{n1}  c}$$ Combining all the above, we now have a recurrence of $F_p(n1,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{align*} \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{align*}$$ 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.
This question is marked "community wiki".
asked 21 Jun '15, 22:13

@kevinsogo This is a very good editorial. learned a lot. thanks answered 19 Jun '16, 14:12

@kevinsogo your editorials are always great! :D
@ironmandhruv thanks! I really appreciate the feedback :)