Birthday (Codeforces 1637G)
Tags: Greedy, constructive algorithms

Vitaly gave Maxim $$$n$$$ numbers $$$1, 2, \ldots, n$$$ for his $$$16$$$-th birthday. Maxim was tired of playing board games during the celebration, so he decided to play with these numbers. In one step Maxim can choose two numbers $$$x$$$ and $$$y$$$ from the numbers he has, throw them away, and add two numbers $$$x + y$$$ and $$$|x - y|$$$ instead. He wants all his numbers to be equal after several steps and the sum of the numbers to be minimal.Help Maxim to find a solution. Maxim's friends don't want to wait long, so the number of steps in the solution should not exceed $$$20n$$$. It is guaranteed that under the given constraints, if a solution exists, then there exists a solution that makes all numbers equal, minimizes their sum, and spends no more than $$$20n$$$ moves.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 25\,000$$$) — the number of test cases.Each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^4$$$) — the number of integers given to Maxim.It is guaranteed that the total sum of $$$n$$$ doesn't exceed $$$5 \cdot 10^4$$$.

Output: For each test case print $$$-1$$$ if it's impossible to make all numbers equal.Otherwise print a single integer $$$s$$$ ($$$0 \le s \le 20n$$$) — the number of steps. Then print $$$s$$$ lines. The $$$i$$$-th line must contain two integers $$$x_i$$$ and $$$y_i$$$ — numbers that Maxim chooses on the $$$i$$$-th step. The numbers must become equal after all operations.Don't forget that you not only need to make all numbers equal, but also minimize their sum. It is guaranteed that under the given constraints, if a solution exists, then there exists a solution that makes all numbers equal, minimizes their sum, and spends no more than $$$20n$$$ moves.


Sample Inputs:
2
2
3

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

Solution (Python):
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]

def pow2(n, mul):
    if n == 2:
        return [[], [mul, 2 * mul]]
    elif n == 1:
        return [[], [mul]]
    elif n == 0:
        return [[], []]
    i = 1
    while 2 * i < n:
        i *= 2
    comb = []
    out = []
    if n == 2 * i:
        out.append(n * mul)
        big = n - 1
    else:
        big = n
    diff = 1
    out.append(i * mul)
    while i + diff <= big:
        comb.append((mul * (i + diff), mul * (i - diff)))
        out.append(2 * mul * i)
        diff += 1
    (a, b) = pow2(diff - 1, 2 * mul)
    comb.extend(a)
    out.extend(b)
    (a, b) = pow2(i - diff, mul)
    comb.extend(a)
    out.extend(b)
    return [comb, out]
(t,) = I()
for _ in range(t):
    (n,) = I()
    if n == 2:
        print(-1)
        continue
    else:
        (comb, out) = pow2(n, 1)
        count = {1 << i: 0 for i in range(17)}
        count[0] = 0
        for guy in out:
            count[guy] += 1
        big = max(out)
        curr = 1
        while 2 * curr < big:
            for i in range(count[curr] // 2):
                comb.append((curr, curr))
                count[2 * curr] += 1
                count[0] += 1
            for i in range(count[curr] % 2):
                comb.append((curr, 2 * curr))
                comb.append((curr, 3 * curr))
                count[4 * curr] += 1
            curr *= 2
        for i in range(count[curr] // 2):
            comb.append((curr, curr))
            count[2 * curr] += 1
            count[0] += 1
        for i in range(count[curr] % 2):
            comb.append((curr, 0))
            comb.append((curr, curr))
            count[2 * curr] += 1
        for i in range(count[0]):
            comb.append((2 * curr, 0))
        print(len(comb))
        for guy in comb:
            print(*guy)

Solution (Python):
import sys
input = sys.stdin.readline
out = []
p2 = []
curr = 1
for i in range(2 * 10 ** 5):
    if i >= curr:
        curr *= 2
    p2.append(curr)
t = int(input())
for _ in range(t):
    ops = []
    l = []
    n = int(input())
    if n == 2:
        out.append(-1)
        continue

    def solve(m, mult):
        if m <= 2:
            for i in range(m):
                l.append((i + 1) * mult)
            return
        up = p2[m]
        l.append(mult * (up // 2))
        for i in range(up // 2 + 1, m + 1):
            ops.append((mult * i, mult * (up - i)))
            l.append(mult * up)
        solve(up - m - 1, mult)
        solve(m - up // 2, mult * 2)
    solve(n, 1)
    zc = 0
    curr = set()
    mx = p2[n - 1]
    mxc = 0

    def add(v):
        global zc, mxc
        if v in curr:
            curr.remove(v)
            ops.append((v, v))
            zc += 1
            add(2 * v)
        elif v == mx:
            mxc += 1
        else:
            curr.add(v)
    for v in l:
        assert v <= mx
        add(v)
    assert zc > 0
    for v in sorted(curr):
        while v != mx:
            ops.append((v, 0))
            ops.append((v, v))
            v *= 2
    while zc:
        ops.append((mx, 0))
        zc -= 1
    out.append(len(ops))
    for (u, v) in ops:
        out.append(str(u) + ' ' + str(v))
print('\n'.join(map(str, out)))

Solution (Python):
import sys, io, os
try:
    Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
    Z = lambda : sys.stdin.readline().encode()
Y = lambda : map(int, Z().split())

def f(k, p):
    global E, c
    if k == 1:
        c[p] += 1
        return
    b = k.bit_length()
    n = 1 << b
    for i in range((n >> 1) + 1, k + 2, 2):
        E.append(f'{i << p} {n - i << p}')
        c[b + p] += 1
    f(k + k - n >> 1, p + 1)
    if n - k > 1:
        f(n - k - 2, p)
O = []
for _ in range(*Y()):
    n = int(Z())
    if n == 2:
        O.append('-1')
        continue
    if n == 1 << n.bit_length() - 1:
        n -= 1
    b = n.bit_length()
    N = 1 << b
    E = []
    c = [0] * 20
    for i in range(20):
        if not n:
            break
        f(n - (1 ^ n & 1), i)
        n >>= 1
    for i in range(20):
        if c[i] > 1:
            E.append(f'{1 << i} {1 << i}')
            c[i] -= 2
            c[i + 1] += 1
            break
    x = 0
    while x < b:
        for i in range(c[x]):
            E.append(f'{1 << x} 0')
            E.append(f'{1 << x} {1 << x}')
            c[x + 1] += 1
        x += 1
    E.append(f'{N} 0')
    O.append(str(len(E)))
    O.extend(E)
print('\n'.join(O))