Matching Numbers (Codeforces 1788C)
Tags: Greedy, constructive algorithms

You are given an integer $$$n$$$. Pair the integers $$$1$$$ to $$$2n$$$ (i.e. each integer should be in exactly one pair) so that each sum of matched pairs is consecutive and distinct. Formally, let $$$(a_i, b_i)$$$ be the pairs that you matched. $$$\{a_1, b_1, a_2, b_2, \ldots, a_n, b_n\}$$$ should be a permutation of $$$\{1, 2, \ldots, 2n\}$$$. Let the sorted list of $$$\{a_1+b_1, a_2+b_2, \ldots, a_n+b_n\}$$$ be $$$s_1 < s_2 < \ldots < s_n$$$. We must have $$$s_{i+1}-s_i = 1$$$ for $$$1 \le i \le n - 1$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.For each test case, a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) is given.It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output: For each test case, if it is impossible to make such a pairing, print "No".Otherwise, print "Yes" followed by $$$n$$$ lines.At each line, print two integers that are paired.You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.If there are multiple solutions, print any.

Note: For the third test case, each integer from $$$1$$$ to $$$6$$$ appears once. The sums of matched pairs are $$$4+2=6$$$, $$$1+6=7$$$, and $$$3+5=8$$$, which are consecutive and distinct.

Sample Inputs:
4
1
2
3
4

Sample Outputs:
Yes
1 2
No
Yes
1 6
3 5
4 2
No

Solution (Python):
import collections
import heapq
import math
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def li():
    return [int(i) for i in input().split()]

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()

def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1

def gcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return (x, y, a)
    (x, y, g) = gcd(b, a % b)
    return (y, x - a // b * y, g)
mod = 998244353
is_prime = [True] * (10 ** 6 + 1)
primes = []

def primeseive(n):
    is_prime[0] = is_prime[1] = False
    for i in range(4, n + 1, 2):
        is_prime[i] = False
    i = 3
    while i * i <= n:
        if is_prime[i] == True:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
        i += 2
    for i in range(n):
        if is_prime[i]:
            primes.append(i)

def solve():
    n = ii()
    if n % 2 == 0:
        return 'No'
    print('Yes')
    ans = ''
    first = 3 * (n + 1) // 2
    for i in range((n + 1) // 2, 0, -1):
        ans += f'{i} {first - i}\n'
        first += 1
    for i in range(n, (n + 1) // 2, -1):
        ans += f'{i} {first - i}\n'
        first += 1
    return ans

def main():
    for _ in range(ii()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import socket
hostnames = ['N551J', 'FVFH32CDQ05N', 'X553M']
input_file = 'c1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)

def read_int_list():
    return list(map(int, input().split()))

def read_int():
    return int(input())

def read_str_list():
    return input().split()

def read_str():
    return input()

def solve():
    t = read_int()
    r = []
    for _ in range(t):
        n = read_int()
        res = []
        if n == 1:
            res = [[1, 2]]
        elif n % 2 == 1:
            res = []
            m = (n - 1) // 2
            j = 2 * n - m + 1
            for i in range(1, m + 1):
                res.append([i, j])
                j += 1
            j = n + 1
            for i in range(m + 1, n + 1):
                res.append([i, j])
                j += 1
        res = [' '.join(map(str, x)) for x in res]
        if len(res) == 0:
            r.append('No')
        else:
            r.append('Yes')
            r.append('\n'.join(res))
    return r

def main():
    res = solve()
    print(*res, sep='\n')
if __name__ == '__main__':
    main()

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    if n % 2 == 0:
        print('No')
        continue
    print('Yes')
    for i in range(1, n + 1):
        x = n // 2
        if i <= x:
            print(i, i + n + x + 1)
        else:
            print(i, i - x + n)