Missing Subsequence Sum
Contest: Codeforces Round 941 (Div. 1)
Difficulty rating: 1800
Tags: bitmasks, constructive algorithms, greedy, number theory

You are given two integers $$$n$$$ and $$$k$$$. Find a sequence $$$a$$$ of non-negative integers of size at most $$$25$$$ such that the following conditions hold.

- There is no subsequence of $$$a$$$ with a sum of $$$k$$$.
- For all $$$1 \le v \le n$$$ where $$$v \ne k$$$, there is a subsequence of $$$a$$$ with a sum of $$$v$$$.

A sequence $$$b$$$ is a subsequence of $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) elements, without changing the order of the remaining elements. For example, $$$[5, 2, 3]$$$ is a subsequence of $$$[1, 5, 7, 8, 2, 4, 3]$$$.

It can be shown that under the given constraints, a solution always exists.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.

Each test case consists of a single line containing two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le k \le n$$$) — the parameters described above.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^7$$$.

Output format:
The first line of output for each test case should contain a single integer $$$m$$$ ($$$1 \le m \le 25$$$) — the size of your chosen sequence.

The second line of output for each test case should contain $$$m$$$ integers $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of your chosen sequence.

If there are multiple solutions, print any.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, we just need a subsequence that adds up to $$$1$$$, but not one that adds up to $$$2$$$. So the array $$$a=[1]$$$ suffices.

In the second example, all elements are greater than $$$k=1$$$, so no subsequence adds up to $$$1$$$. Every other integer between $$$1$$$ and $$$n$$$ is present in the array, so there is a subsequence of size $$$1$$$ adding up to each of those numbers.

Example input:
5
2 2
6 1
8 8
9 3
10 7

Example output:
1
1
5
2 3 4 5 6
7
1 1 1 1 1 1 1
4
7 1 4 1
4
1 2 8 3

Editorial:
Notice that for a fixed $$$k$$$, a solution for $$$n=c$$$ is also a solution for all $$$n < c$$$. So we can ignore the value of $$$n$$$ and just assume it's always $$$10^6$$$.
If we didn't have the restriction that no subsequence can add up to $$$k$$$, the most natural solution would be $$$[1, 2, 4, 8, \cdots 2^{19}]$$$. Every value from $$$1$$$ to $$$10^6$$$ appears as the sum of the subsequence given by its binary representation. We will use a modified version of this array to solve the problem.
Let $$$i$$$ be the largest integer such that $$$2^i \le k$$$. We will use this array (of size $$$22$$$):
$$$a=[k-2^i, k+1, k+1+2^i, 1, 2, 4, ... 2^{i-1}, 2^{i+1}, ... 2^{19}]$$$
To prove that no subsequence of $$$a$$$ adds up to $$$k$$$, consider the list of all elements in the array that are at most $$$k$$$, since these are the only ones that could be present in a subsequence adding to $$$k$$$. These are
$$$k-2^i, 1, 2, 4, ... 2^{i-1}$$$
Since these add up to $$$k-1$$$, no subsequence can add up to $$$k$$$.
To prove that for all $$$1 \le v \le n$$$ where $$$v \ne k$$$, there is a subsequence adding up to $$$v$$$, we consider several cases:
• If $$$v < 2^i$$$, we can simply use the binary representation of $$$v$$$.
• If $$$2^i \le v < k$$$, we can first take all of the elements that are at most $$$k$$$ as part of our subsequence. We then need to remove elements with a sum equal to $$$k-1-v$$$. Because $$$2^i \le v < k < 2^{i+1}$$$, $$$k-1-v$$$ is less than $$$2^i$$$, so we can simply remove its binary representation.
• If $$$v > k$$$, we can take $$$k+1$$$ along with the binary representation of $$$v-k-1$$$. The one edge case is when the $$$2^i$$$ bit is set in $$$v-k-1$$$. In this case, we replace $$$k+1$$$ with $$$k+1+2^i$$$.
So in all cases, we can form a subsequence adding up to $$$v$$$.
Complexity: $$$O(\log n)$$$