Mock CCC 25 S3 - Pair Sets
As an aspiring MAT157 student, you must create \(N\) sets of positive integers such that there are \(A\) pairs of sets \((X, Y)\) where \(|X \oplus Y|\) is even and \(B\) pairs of sets \((X, Y)\) where \(|X \oplus Y|\) is odd. Every set in your collection must be unique, each with at most \(K\) elements and with each element of each set being at most \(M\).
Construct the lexicographically smallest collection of sets, or determine that it is impossible.
We denote the set \(X \oplus Y\) as the set of elements that appear in one of \(X\) or \(Y\) but not both \(X\) and \(Y\). Additionally, we denote \(|X \oplus Y|\) as the number of elements in \(X \oplus Y\). Your sets must also be valid sets, so your sets cannot be empty nor have duplicate elements.
Collection \(C\) is lexicographically smaller than collection \(D\) if at the first index of difference \(i\) between the two, \(C_{i}\) is lexicographically smaller than \(D_{i}\) or \(C_{i}\) does not exist. Additionally, set \(A\) is lexicographically smaller than set \(B\) if at the first index of difference \(i\) between the two, \(A_{i}\) is lexicographically smaller than \(B_{i}\) or \(A_{i}\) does not exist.
Constraints
| Subtask | Marks Awarded | \(N\) | \(A\) | \(B\) | \(K\) | \(M\) |
|---|---|---|---|---|---|---|
| Subtask 1 | 2 Marks | \(1 \le N \le 4\) | \(0 \le A \le 10\) | \(0 \le B \le 10\) | \(1 \le K \le 2\) | \(1 \le M \le 2\) |
| Subtask 2 | 5 Marks | \(1 \le N \le 20\) | \(0 \le A \le 10^{3}\) | \(0 \le B \le 10^{3}\) | \(1 \le K \le 6\) | \(1 \le M \le 6\) |
| Subtask 3 | 8 Marks | \(1 \le N \le 10^{5}\) | \(0 \le A \le 10^{10}\) | \(0 \le B \le 10^{10}\) | \(1 \le K \le 20\) | \(1 \le M \le 20\) |
Input Specification
The first line and only line contains five integers, \(N\), \(A\), \(B\), \(K\), and \(M\).
Output Specification
Output \(N\) lines, one for each set in your collection. For each line, output the size and the elements of the respective set, all space-separated. Ensure that your collection is the lexicographically smallest collection of sets possible.
If it is impossible to construct such a collection, output -1 instead.
Sample Input 1
3 1 2 6 6Sample Output 1
3 1 4 5
6 1 2 3 4 5 6
2 1 6Explanation for Sample Output 1
Let \(S\) be the one-indexed collection of all sets. Here, \(S_{1} \oplus S_{2} = \{ 2, 3, 6 \}\), \(S_{1} \oplus S_{3} = \{ 4, 5, 6 \}\), and \(S_{2} \oplus S_{3} = \{ 2, 3, 4, 5 \}\). However, this output would score \(0\) points since it is not the lexicographically smallest collection.
Sample Input 2
4 0 0 1 1Sample Output 2
-1Explanation for Sample Output 2
It can be shown that it is impossible to construct such a collection of sets.
Comments