USACO 2025 US Open Contest, Silver
Problem 1. Sequence Construction
Contest has ended.
Log in to allow submissions in analysis mode
Lately, the cows on Farmer John's farm have been infatuated with watching the show Apothecowry Dairies. The show revolves around a clever bovine sleuth CowCow solving problems of various kinds. Bessie found a new problem from the show, but the solution won't be revealed until the next episode in a week! Please solve the problem for her.
You are given integers $M$ and $K$ $(1 \leq M \leq 10 ^ 9, 1 \leq K \leq 31)$. Please choose a positive integer $N$ and construct a sequence $a$ of $N$ non-negative integers such that the following conditions are satisfied:
- $1 \le N \le 100$
- $a_1 + a_2 + \dots + a_N = M$
- $\text{popcount}(a_1) \oplus \text{ popcount}(a_2) \oplus \dots \oplus \text{ popcount}(a_N) = K$
If no such sequence exists, print $-1$.
$\dagger \text{ popcount}(x)$ is the number of bits equal to $1$ in the binary representation of the integer $x$. For instance, the popcount of $11$ is $3$ and the popcount of $16$ is $1$.
$\dagger \oplus$ is the bitwise xor operator.
The input will consist of $T$ ($1 \le T \le 5 \cdot 10^3$) independent test cases.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains $T$.
The first and only line of each test case has $M$ and $K$.
It is guaranteed that all test cases are unique.
OUTPUT FORMAT (print output to the terminal / stdout):
Output the solutions for $T$ test cases as follows:
If no answer exists, the only line for that test case should be $-1$.
Otherwise, the first line for that test case should be a single integer $N$, the length of the sequence -- ($1 \le N \le 100$).
The second line for that test case should contain $N$ space-separated integers that satisfy the conditions -- ($0 \le a_i \le M$).
SAMPLE INPUT:
3 2 1 33 5 10 5
SAMPLE OUTPUT:
2 2 0 3 3 23 7 -1
In the first test case, the elements in the array $a = [2, 0]$ sum to $2$. The xor sum of popcounts is $1 \oplus 0 = 1$. Thus, all the conditions are satisfied.
In the second test case, the elements in the array $a = [3, 23, 7]$ sum to $33$. The xor sum of the popcounts is $2 \oplus 4 \oplus 3 = 5$. Thus, all conditions are satisfied.
Other valid arrays are $a = [4, 2, 15, 5, 7]$ and $a = [1, 4, 0, 27, 1]$.
It can be shown that no valid arrays exist for the third test case.
SCORING:
- Input 2: $M \leq 8, K \leq 8$
- Inputs 3-5: $M > 2^K$
- Inputs 6-18: No additional constraints.
Problem credits: Aakash Gokhale