Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
You win the final game of a tournament bracket iff you are the highest ranked player in that bracket. For example, in a tournament with 
~8~ people, you win your first game iff you are the better player in your 
~2~-player bracket, your second game iff you are the best player in your 
~4~-player bracket, and your third game iff you are the best player among all ~8~ people. If we can find the probability that you win your 
~i^\text{th}~ game using this, then we can use the linearity of expectation to sum these probabilities up to get our final answer.
So what is the probability that you win your ~i^\text{th}~ game? Well, there are 
~2^k~ players in all, 
~2^i~ players in this particular bracket, and 
~r-1~ players better than you (or equivalently, 
~2^k-r~ players worse than you). You win in the event that of the 
~2^i-1~ other players in your bracket, all of them are chosen from the ~2^k-r~ players that are worse than you. Since all brackets are equally likely, this happens with probability:
$$\displaystyle \binom{2^k-r}{2^i-1} / \binom{2^k-1}{2^i-1}$$
It's dangerous to compute these two values directly and then divide them, since these are both very big numbers. We have two options for dealing with this:
- We can work with logarithms of factorials instead of factorials directly.
- We can do some simplification of the expression by cancelling common terms.
Comments
bruh isn't the formula obviously wrong? the numerator is larger than the denominator :thinking: The correct formula should be
fixed