hackercupai/hackercup huggingface dataset:
First note that, for a set of blocks, it does not matter how they are distributed between the players. That is, if two blocks get swapped this will not change the outcome (possible or not to have difference of d). This comes from the fact that for a given distribution of blocks, we can always form two towers of equal height (with height being the LCM of all elements in the set).

With that, we can effectively either remove or add a block with height \(H_i\) to a tower, which corresponds to either adding or subtracting \(H_i\) to the current difference between the towers. It is a well known result that given integers \((a,b)\), with the equation \(a*x + b*y = k\), where \(x\) and \(y\) can assume any integer values, \(k\) can assume any value that is a multiple of \(\text{gcd}(a,b)\). This results can is also valid for multiple variables (see Bézout's identity). For a given set of blocks, we can make it so that the difference assumes any value that is a multiple of the gcd of the chosen blocks.

Now the problem simplifies to, for each divisor \(d\) of \(D\), consider how many subsets of size \(K\) are there such that the gcd is \(d\). This can be solved in \(\mathcal{O}(MAXV/i)\). It is easy to convert this problem to, how many subsets of size \(k\) are there such that GCD of values is \(1\). This final problem can be solved with Inclusion-Exclusion principle: for each integer \(x\), it is easy to count how many subsets of size \(k\) are there such that the gcd is a multiple of \(x\) (let's call this \(f(x)\)), this is simply \(\binom{\text{freq}[x]}{k}\) where \(\text{freq}[x]\) is how many integers are divisible by \(x\). The solution is

\[\sum_{x=1}^{MAXV} [f(x)*\mu(x)]\]

where \(\mu(x)\) is the Mobious function (that is, for square free integers, \(\mu(x)\) is \(1\) if \(x\) has an even number of prime factors, or \(-1\) if it has an odd number of prime factors, which is related to inclusion exclusion). This works in \(\mathcal{O}(N \log N)\) for any value of \(K\), not necessarily \(K \le 20\).