hackercupai/hackercup huggingface dataset:
The problem is asking: "Out of a uniformly randomly chosen subset of \(K+1\) cookies, what is the probability that the heaviest cookie (with ties broken uniformly randomly) is from batch \(1\)?" Note that it's irrelevant how ties are broken by choosing the left cookie, because for any random subset lined up in a random order to be place on the scale, it's equally likely for any two cookies of the same weight to be placed on either side.

Let \(X\), \(Y\), and \(Z\) be the numbers of cookies outside of batch \(1\) that weigh less than, equal to, and greater than \(W_1\), respectively. Let \(M = C_1 + X + Y + Z\) be the total number of cookies. Note that if \(C_1 + X + Y < K + 1\), then any size \(K+1\) subset must contain at least \(1\) cookie heavier than \(W_1\), in which case the answer is \(0\). Otherwise, the answer is determined as follows:

1. There are \(\binom{C_1 + X + Y}{K+1}\) ways to pick \(K+1\) cookies that are not heavier than \(W_1\).
2. There are \(\binom{X}{K+1}\) ways to pick \(K+1\) cookies that are strictly lighter than \(W_1\).
3. The number of ways to pick at least \(1\) cookie of weight equal to \(W_1\) (some, none, or all from batch \(1\)) is the first number minus the second number.
4. The probability of picking at least \(1\) cookie of weight equal to \(W_1\) is equal to the previous number divided by \(\binom{M}{K + 1}\) (the total number of ways to pick \(K+1\) cookies).
5. The conditional probability of a tie being broken with a batch \(1\) cookie out of all equal weight cookies picked (*given* that we picked at least \(1\) equal weight cookie) is equal to \(\frac{C_1}{C_1 + Y}\). Note that this is independent of any attributes of a specific chosen subset, as each cookie of weight equal to \(W_1\) has the same \(\frac{C_1}{C_1 + Y}\) chance of being a batch \(1\) cookie.
6. The final answer is the product of the previous two values (the conditional probability times the prior probability).

If we precompute factorials up to \(M\) in \(\mathcal{O}(M)\) time, then each binomial coefficient can be computed in time \(\mathcal{O}(1)\), plus the time to compute a mod-inverse. After that, there are only a constant number of modular arithmetic steps, which we can perform in \(\mathcal{O}(1)\) as well.

[See David Harmeyer's solution video here.](https://www.youtube.com/watch?v=rg0Q73SMhUM)