And Matching
Contest: Codeforces Round 768 (Div. 1)
Difficulty rating: 1500
Tags: bitmasks, constructive algorithms

You are given a set of $$$n$$$ ($$$n$$$ is always a power of $$$2$$$) elements containing all integers $$$0, 1, 2, \ldots, n-1$$$ exactly once.

Find $$$\frac{n}{2}$$$ pairs of elements such that:

- Each element in the set is in exactly one pair.
- The sum over all pairs of the bitwise AND of its elements must be exactly equal to $$$k$$$. Formally, if $$$a_i$$$ and $$$b_i$$$ are the elements of the $$$i$$$-th pair, then the following must hold: $$$$$$\sum_{i=1}^{n/2}{a_i \& b_i} = k,$$$$$$ where $$$\&$$$ denotes the bitwise AND operation.

If there are many solutions, print any of them, if there is no solution, print $$$-1$$$ instead.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 400$$$) — the number of test cases. Description of the test cases follows.

Each test case consists of a single line with two integers $$$n$$$ and $$$k$$$ ($$$4 \leq n \leq 2^{16}$$$, $$$n$$$ is a power of $$$2$$$, $$$0 \leq k \leq n-1$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$2^{16}$$$. All test cases in each individual input will be pairwise different.

Output format:
For each test case, if there is no solution, print a single line with the integer $$$-1$$$.

Otherwise, print $$$\frac{n}{2}$$$ lines, the $$$i$$$-th of them must contain $$$a_i$$$ and $$$b_i$$$, the elements in the $$$i$$$-th pair.

If there are many solutions, print any of them. Print the pairs and the elements in the pairs in any order.

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

Note:
In the first test, $$$(0\&3)+(1\&2) = 0$$$.

In the second test, $$$(0\&2)+(1\&3) = 1$$$.

In the third test, $$$(0\&1)+(2\&3) = 2$$$.

In the fourth test, there is no solution.

Example input:
4
4 0
4 1
4 2
4 3

Example output:
0 3
1 2
0 2
1 3
0 1
2 3
-1

Editorial:
Let's define $$$c(x)$$$, the compliment of $$$x$$$, as the number $$$x$$$ after changing all bits 0 to 1 and vice versa, for example $$$c(110010_2) = 001101_2$$$.
It can be shown that $$$c(x) = x\oplus{(n-1)}$$$. Remember that $$$n-1 = 11...11_2$$$ since $$$n$$$ is a power of $$$2$$$.
We will describe a constructive approach to the problem. We will separate the problem into three cases.
• Case $$$k = 0$$$: In this case it is possible to pair $$$x$$$ with $$$c(x)$$$ for $$$0\leq{x}<{\frac{n}{2}}$$$, getting $$$\sum\limits_{x=0}^{\frac{n}{2}-1} {x\&{c(x)}} = 0$$$.
• Case $$$0 < k < n-1$$$: In this case it is possible to pair each element with its compliment except $$$0$$$, $$$k$$$, $$$c(k)$$$ and $$$n-1$$$, and then pair $$$0$$$ with $$$c(k)$$$ and $$$k$$$ with $$$n-1$$$, $$$0\& c(k) = 0$$$ and $$$k\& (n-1) = k$$$.
• Case $$$k = n-1$$$: There are many constructions that work in this case, if $$$n=4$$$ there is no solution, if $$$n \geq8$$$ it is possible to construct the answer in the following way: It is possible to pair $$$n-1$$$ with $$$n-2$$$, $$$n-3$$$ with $$$1$$$, $$$0$$$ with $$$2$$$ and all other elements with their compliments.   $$$(n-1)\&{(n-2)}=n-2$$$, for example $$$1111_2\&{1110_2}=1110_2$$$  $$$(n-3)\&{1}=1$$$, for example $$$1101_2\&{0001_2}=0001_2$$$  $$$0\&{2}=0$$$, for example $$$0000_2\&{0010_2}=0000_2$$$  All other elements can be paired with their complements and $$$x\&{c(x)}=0$$$  Note that $$$(n-2)+1+0+0+ ... +0=n-1$$$.
• $$$(n-1)\&{(n-2)}=n-2$$$, for example $$$1111_2\&{1110_2}=1110_2$$$
• $$$(n-3)\&{1}=1$$$, for example $$$1101_2\&{0001_2}=0001_2$$$
• $$$0\&{2}=0$$$, for example $$$0000_2\&{0010_2}=0000_2$$$
• All other elements can be paired with their complements and $$$x\&{c(x)}=0$$$
Each case can be implemented in $$$O(n)$$$.
There are also non-constructive approaches, however, they are more complicated, I will explain two of them briefly.
Let's define $$$a$$$ such that $$$a_i = i-1$$$ for $$$1\le i \le \frac{n}{2}$$$ and $$$b$$$ such that $$$b_i = c(a_i)$$$ for $$$1\le i \le \frac{n}{2}$$$.
For example, for $$$n = 16$$$ they are:
$$$$$$a = [0000_2, 0001_2, 0010_2, 0011_2, 0100_2, 0101_2, 0110_2, 0111_2]$$$$$$
$$$$$$b = [1111_2, 1110_2, 1101_2, 1100_2, 1011_2, 1010_2, 1001_2, 1000_2]$$$$$$
All swaps are independent and are applied to the original $$$a$$$ and $$$b$$$.
After swapping two adjacent elements of $$$b$$$ (that have not been swapped) the sum will change in $$$2^x-1$$$ for some positive integer $$$x$$$.
Then it is possible to solve the problem by repeatedly swapping the pair that maximizes $$$\sum\limits_{i=1}^{n/2}{a_i\&b_i}$$$ after the swap such that $$$\sum\limits_{i=1}^{n/2}{ a_i\&b_i} \leq k$$$ is held and none of its elements have been swapped yet.
However, this only works for all values of $$$k$$$ if $$$n \geq 32$$$, the case $$$n \leq 16$$$ can be handled with brute force.
There is also a randomized solution involving swapping elements from $$$b$$$ on these arrays $$$a$$$ and $$$b$$$.
It is possible to start with $$$a$$$ and $$$b$$$ and repeatedly select and index $$$x$$$ randomly and swap $$$b_x$$$ with $$$b_{x+1}$$$ if $$$\sum\limits_{i=1}^{n/2}{a_i\&b_i} \leq k$$$ holds until $$$\sum\limits_{i=1}^{n/2}{a_i\&b_i} = k$$$.
We have no proof of this solution but it was stressed against each possible input to the problem and it worked quickly for $$$n \geq 16$$$, the case $$$n \leq 8$$$ can be handled with brute force.