You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a random way, so that when player $i$ faces player $j$, he wins with probability $\frac{\operatorname{rk}(i)}{\operatorname{rk}(i)+\operatorname{rk}(j)}$. When a player loses a game, he gets knocked out of the tournament, thus the tournament finishes in $k$ rounds.
You are requested to arrange the players into a knockout tournament starting line-up (i.e. on the leaves of a complete binary tree of height $k$) in the way that maximizes the probability that player $1$ wins the tournament.
The official greedy solution, presented without any trace of proof, is the following:
- Sort the players $1, r_2, r_3, \dots r_{2^k}$, where $r_2, \dots r_{2^k}$ are the players $2 \dots 2^k$ sorted in ascending order of their rank.
- Arrange players $1, \dots, 2^{k-1}$ in the left-subtree and $2^{k-1} + 1, \dots 2^k$ in the right subtree and recurse.
- For each node $v$ of the tree compute (bottom-up using dynamic programming) the probability vector $P_v$ such that $P_v[x]$ is the probability of player $x$ winning the sub-tournament rooted at $v$.
This algorithm runs in $\mathcal{O}(n^2 \log n)$.
How to prove that the algorithm is also correct?
The original problem is from ICPC NWERC 2017 (problem K). Here we posted a simplified version.
