hackercupai/hackercup huggingface dataset:
This problem can be solved with dynamic programming. Let \(E_{b, w}\) be the expected number of future matches which a player will be present for given that they're currently in the tournament together with \(b\) better and \(w\) worse players than them. The \(i\)th output (the expected number of matches for which player \(i\) will be present) will then be \(E_{N - i, i - 1}\).

Let's define \(F_{b, w}\) similarly to \(E_{b, w}\), except with the additional constraint that the winner of the next match is guaranteed to be the higher-skilled of the two competitors. We'll define \(G_{b, w}\) in much the same way, except with the next match's winner being the lower-skilled competitor. We then have \(E_{b, w} = F_{b, w} * P + G_{b, w} * (1 - P)\).

We'll next consider how to compute \(F_{b, w}\), noting that \(G_{b, w}\) may then be computed very similarly. \(F_{b, w}\) is equal to \(1\) (as the player will certainly be present for the next match) plus the expected number of matches the player will be present after the next match (if they're not eliminated in it). If they're not about to be eliminated, then either a better or a worse player must be eliminated instead. Let \(Q(x) = \frac{x(x - 1)}{2}\) (the number of unordered pairs out of \(x\) players). If \(b > 0\), then there's a \(\frac{Q(b)}{Q(b + w + 1)}\) chance that a better player will be eliminated, meaning that we should add \(E_{b-1, w} * \frac{Q(b)}{Q(b + w + 1)}\) onto \(F_{b, w}\). Similarly, if \(w > 0\), we should add \(E_{b, w-1} * \frac{w(b+1) + Q(w)}{Q(b + w + 1)}\) onto \(F_{b, w}\).

Over the course of the algorithm, we'll compute \(E_{b, w}\) for \(O(N^2)\) pairs of \(b\) and \(w\). Computing each such value takes constant time, resulting in a time complexity of \(O(N^2)\).