hackercupai/hackercup huggingface dataset:
If we draw an edge for each \((A_i, B_i)\), we'll get a graph of the \(N\) students. It's clear that to avoid splitting up any of the \(M\) pairs, we have to avoid splitting up any connected component in the graph. From here, we see that what only the component sizes matter, which can be found with a simple breadth- or depth-first search.

Fixing \(K\), the problem reduces to checking whether the array of component sizes can be partitioned into \(K\) subsets of equal sum. First, if \(N\) is not a multiple of \(K\), then we cannot partition \(N\) into equal-sized groups of size \(N / K\). Otherwise, we'll need to find a valid partition.

Consider a backtracking algorithm that attempts to recursively assign each component to one of the \(K\) groups. We will maintain a size \(K\) array of current group sizes, and only assign to a group if the new size doesn't exceed the target size of \(N / K\). Clearly, this naive method is exponential, and will not be fast enough as we have up to \(100\) components/groups.

One optimization is to observe that for a current state (array of partially-assigned group sizes), e.g. \([1, 1, 1, 2, 0, 3]\), adding to any one of identical groups is the same, so we only have to recurse for one of them. Instead of an array, we can think of the state as a *multiset* of numbers with sum not exceeding \(N\). We can maintain a set of multisets to track states we've already seen and avoid recomputing them. Each group can take on sizes \(0...\frac{N}{K}\) (i.e. \(\frac{N}{K} - 1\) different values). The number of states is the number of ways to choose \(\frac{N}{K} + 1\) elements to fill \(K\) slots with repetition allowed. This is \((\frac{N}{K} + 1)\) [multichoose](https://mathworld.wolfram.com/Multichoose.html) \(K\), equal to \(\bigl( \binom{N/K + 1}{K} \bigr) = \binom{N/K + K}{K} \). At worst, this comes out to \(\approx185{,}000\) states when \(\frac{N}{K}=K=10\).

The overall time complexity will be bounded by the number of \(K\)s to check (a.k.a the number of divisors of \(N\), here at most \(12\) for \(N = 60 \le 100\)) multiplied by the number of states, multiplied by the time to process each state. In practice, the jury's solution solves the full dataset in under a few seconds on a modest system.