Subtask 1 [2 Marks]

This subtask rewarded solutions that used brute force or casework. Note that \(A + B = \frac{N(N - 1)}{2}\) must be true for a valid construction to exist.

Time Complexity: \(O((NK)!)\) or \(O(1)\)

Subtask 2 [5 Marks]

This subtask rewarded solutions that used exponential time and not factorial time.

Time Complexity: \(O(2^{N} \text{ max}(K, M))\)

Subtask 3 [8 Marks]

For the sake of problem solving, let's assume that \(M\) is sufficiently greater than \(N\), allowing multiple valid elements per set.

We first fix each element to one set, with the consequence that no sets overlap any elements. This implies that \(|X \oplus Y| = |X| + |Y|\), and that the parity of \(|X \oplus Y|\) is based on the parities of \(|X|\) and \(|Y|\).

Let \(O\) be the number of sets that have an odd number of elements and \(E\) be the number of sets that have an even number of elements. A valid construction exists if \(A = \frac{O(O - 1)}{2} + \frac{E(E - 1)}{2}\) and \(B = OE\). Clearly, \(O + E = N\), so the values of \(O\) and \(E\) can be found in linear time.

We now need to deal with sets that share elements. To this extent, let \(X\) and \(Y\) be two sets that share \(z\) elements. Then, \(X \oplus Y\) contains exactly the elements of \(X\) and \(Y\), but with each of the \(z\) elements removed twice, one for each appearance in \(X\) and \(Y\). As such, \(|X \oplus Y| = |X| + |Y| - 2z\). Since \(2z\) is always even, our observation about the parity of \(|X \oplus Y|\) continues to hold.

Constructing the collection of sets is trivial - a set either contains an element or not, so there are at most \(2^{M}\) possible sets. Brute force can be used to compute the first \(E\) even sized sets and the first \(O\) odd sized sets. Obviously, if an insufficient amount of sets exist, output as such.

Time Complexity: \(O(N \text{ max}(K, M))\)

Author's Note: Originally, subtask 2 had specific constraints to lead contestants to the full solution in subtask 3 by allowing for each set to have distinct elements. However, this required a custom checker - something we could not get working. You should still expect S3's on the CCC to have working custom checkers, and therefore, better subtasks.