And Matching (Codeforces 1630A)
Tags: Others, bitmasks

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: 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: 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.

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.

Sample Inputs:
4
4 0
4 1
4 2
4 3

Sample Outputs:
0 3
1 2
0 2
1 3
0 1
2 3
-1

Solution (Python):
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().strip().split())
    if k == n - 1:
        if n == 4:
            print('-1')
            continue
        print(f'{n - 2} {n - 1}')
        print(f'1 3')
        print(f'0 {n - 4}')
        print(f'2 {n - 3}')
        for x in range(4, n // 2):
            print(f'{x} {n - x - 1}')
        continue
    if k == 0:
        for x in range(n // 2):
            print(f'{x} {n - x - 1}')
        continue
    print(f'{k} {n - 1}')
    print(f'0 {n - k - 1}')
    for x in range(1, n // 2):
        if x in (k, n - k - 1):
            continue
        print(f'{x} {n - x - 1}')

Solution (Python):
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    if k == n - 1:
        if n == 4:
            print(-1)
        else:
            print(n - 3, n - 1, sep=' ')
            print(2, n - 2, sep=' ')
            print(0, 1, sep=' ')
            for i in range(3, n // 2):
                print(i, n - 1 - i, sep=' ')
        continue
    print(k, n - 1, sep=' ')
    if k != 0:
        print(0, n - 1 - k, sep=' ')
    for i in range(1, n // 2):
        if i != k and n - 1 - i != k:
            print(i, n - 1 - i, sep=' ')

Solution (Python):
case = int(input())
all_answers = []
for i in range(case):
    answers = []
    line = input().split()
    n = int(line[0])
    k = int(line[1])
    if n - 1 == k and n == 4:
        answers.append(-1)
    elif n - 1 == k:
        answers.append(f'{k - 1} {k}')
        answers.append(f'{1} {3}')
        answers.append(f'{0} {n - 1 - 3}')
        numbers = range(0, int(n / 2))
        excluded = {k - 1, k, 0, n - 1 - 3, 1, 3}
        numbers = [number for number in numbers if number not in excluded]
        for number in numbers:
            answers.append(f'{number} {n - number - 1}')
    else:
        answers.append(f'{k} {n - 1}')
        if k != 0:
            answers.append(f'{0} {n - k - 1}')
        numbers = range(0, int(n / 2))
        excluded = {k, n - 1, 0, n - k - 1}
        numbers = [number for number in numbers if number not in excluded]
        for number in numbers:
            answers.append(f'{number} {n - number - 1}')
    answers.sort()
    all_answers.append(answers)
for answers in all_answers:
    for answer in answers:
        print(answer)