Grid Reconstruction (Codeforces 1816B)
Tags: Greedy, constructive algorithms

Consider a $$$2 \times n$$$ grid, where $$$n$$$ is an even integer. You may place the integers $$$1, 2, \ldots, 2n$$$ on the grid, using each integer exactly once.A path is a sequence of cells achieved by starting at $$$(1, 1)$$$, then repeatedly walking either downwards or to the right, and stopping when $$$(2, n)$$$ is reached. The path should not extend beyond the grid.The cost of a path is the alternating sum of the numbers written on the cells in a path. That is, let the numbers written on the cells be $$$a_1, a_2, \ldots, a_k$$$ (in the order that it is visited), the cost of the path is $$$a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1}$$$.Construct a way to place the integers $$$1, 2, \ldots, 2n$$$ on the grid, such that the minimum cost over all paths from $$$(1, 1)$$$ to $$$(2, n)$$$ is maximized. If there are multiple such grids that result in the maximum value, output any of them.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of test cases follows.The first and the only line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$, $$$n$$$ is even) — the number of the columns in the grid.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, output $$$2$$$ lines, each containing $$$n$$$ integers — the desired grid. If there are multiple solutions, output any of them.

Note: In the first test case, there are only two paths from cell $$$(1, 1)$$$ to cell $$$(2, 2)$$$. Their costs are $$$3-1+4=6$$$ and $$$3-2+4=5$$$. Then the minimum cost is $$$5$$$, which is the maximum possible value.In the second test case, there are four paths from cell $$$(1, 1)$$$ to cell $$$(2, 4)$$$. Their costs are $$$8-1+5-3+7=16$$$, $$$8-2+5-3+7=15$$$, $$$8-2+6-3+7=16$$$, and $$$8-2+6-4+7=15$$$. Then the minimum value is $$$15$$$, which is the maximum possible value.

Sample Inputs:
3
2
4
6

Sample Outputs:
3 2
1 4
8 2 6 4
1 5 3 7
11 5 9 1 7 3
6 10 2 8 4 12

Solution (Python):
def construct_grid():
    t = int(input())
    for _ in range(t):
        n = int(input())
        (first_row, second_row) = ('', '')
        high_column = 0
        (even_low, odd_low) = (0, -1)
        (even_high, odd_high) = (n * 2, n * 2 - 1)
        for _ in range(n - 1):
            if high_column:
                even_high -= 2
                odd_high -= 2
                first_row += str(even_high) + ' '
                second_row += str(odd_high) + ' '
                high_column = 0
            else:
                even_low += 2
                odd_low += 2
                first_row += str(even_low) + ' '
                second_row += str(odd_low) + ' '
                high_column = 1
        print(str(n * 2) + ' ' + first_row[:-1] + '\n' + second_row + str(n * 2 - 1))
construct_grid()

Solution (Python):
number_of_tests = int(input())
for _ in range(number_of_tests):
    n = int(input())
    max_n = 2 * n
    min_n = 1
    first_row = ''
    second_row = ''
    for i in range(n):
        if i == 1:
            first_row += f' {min_n}'
            second_row += f' {n + 1}'
            max_n -= 1
            min_n += 1
        elif i == n - 1:
            first_row += f' {min_n}'
            second_row += f' {2 * n - 1}'
            max_n -= 1
            min_n += 1
        elif i % 2 == 0:
            first_row += f' {max_n}'
            second_row += f' {min_n}'
            max_n -= 1
            min_n += 1
        else:
            first_row += f' {min_n}'
            second_row += f' {max_n}'
            max_n -= 1
            min_n += 1
    print(first_row[1:])
    print(second_row[1:])

Solution (Python):
def fun(n):
    a1 = []
    a2 = []
    for i in range(n - 1):
        if i % 2 == 0:
            a1.append(str(i + 1))
            a2.append(str(i + 2))
        else:
            a1.append(str((n - 1) * 2 - i))
            a2.append(str((n - 1) * 2 - i + 1))
    a1.insert(0, str(n * 2 - 1))
    a2.append(str(n * 2))
    print(' '.join(a1))
    print(' '.join(a2))
t = int(input())
for t1 in range(t):
    n = int(input())
    fun(n)