You are not logged in. Please login at www.codechef.com to post your questions!

×

TENNIS - Editorial

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{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's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 01 Jul '15, 22:26

2

@kevinsogo your editorials are always great! :D

(02 Jul '15, 01:39) ironmandhruv4★

@ironmandhruv thanks! I really appreciate the feedback :)

(02 Jul '15, 11:49) kevinsogo7★

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

link

answered 19 Jun '16, 14:12

faceless_man's gravatar image

1★faceless_man
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,490
×2,086
×240
×47

question asked: 21 Jun '15, 22:13

question was seen: 2,387 times

last updated: 19 Jun '16, 14:12