Matrix of Differences (Codeforces 1783B)
Tags: Math, constructive algorithms

For a square matrix of integers of size $$$n \times n$$$, let's define its beauty as follows: for each pair of side-adjacent elements $$$x$$$ and $$$y$$$, write out the number $$$|x-y|$$$, and then find the number of different numbers among them.For example, for the matrix $$$\begin{pmatrix} 1 & 3\\ 4 & 2 \end{pmatrix}$$$ the numbers we consider are $$$|1-3|=2$$$, $$$|1-4|=3$$$, $$$|3-2|=1$$$ and $$$|4-2|=2$$$; there are $$$3$$$ different numbers among them ($$$2$$$, $$$3$$$ and $$$1$$$), which means that its beauty is equal to $$$3$$$.You are given an integer $$$n$$$. You have to find a matrix of size $$$n \times n$$$, where each integer from $$$1$$$ to $$$n^2$$$ occurs exactly once, such that its beauty is the maximum possible among all such matrices.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 49$$$) – the number of test cases.The first (and only) line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 50$$$).

Output: For each test case, print $$$n$$$ rows of $$$n$$$ integers — a matrix of integers of size $$$n \times n$$$, where each number from $$$1$$$ to $$$n^2$$$ occurs exactly once, such that its beauty is the maximum possible among all such matrices. If there are multiple answers, print any of them.


Sample Inputs:
2
2
3

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

Solution (Python):
from itertools import chain
import itertools
import sys

def main():
    input = sys.stdin.readline
    test_cases = int(input())
    while test_cases:
        test_cases -= 1
        n = int(input())
        n_squared = n * n
        array = list(range(1, n_squared + 1))
        array_rev = array[::-1]
        array = list(chain(*zip(array_rev, array)))
        array = array[:n_squared]
        matrix = [array[i * n:(i + 1) * n] if i % 2 == 0 else array[(i + 1) * n - 1:i * n - 1:-1] for i in range(n)]
        print('\n'.join((' '.join(map(str, i)) for i in matrix)))
if __name__ == '__main__':
    main()

Solution (Python):
t = int(input())
result = []
for i in range(t):
    n = int(input())
    m = n ** 2 // 2
    k = n ** 2
    tab = []
    for j in range(1, m + 1):
        tab += [str(k), str(j)]
        k -= 1
    if n % 2 == 1:
        tab.append(str(n ** 2 // 2 + 1))
    h = 0
    for j in range(0, len(tab) - n + 1, n):
        c = tab[j:j + n]
        if h == 0:
            result.append(' '.join(c))
        else:
            c.reverse()
            result.append(' '.join(c))
        h = 1 - h
for i in result:
    print(i)

Solution (Python):
import sys

def in_int():
    return int(sys.stdin.readline())

def in_str():
    return sys.stdin.readline().rstrip()

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

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

def in_arr_str():
    return sys.stdin.readline().split()

def is_prime(n):
    for i in range(2, int(n ** (1 / 2)) + 1):
        if n % i == 0:
            return True
    return False

def bin2dec(s):
    n = 0
    for i in range(len(s)):
        n += int(s[len(s) - i - 1]) * 2 ** i
    return n

def gcd(a, b):
    (a, b) = (max(a, b), min(a, b))
    while b != 0:
        (a, b) = (b, a % b)
    return a

def dec2bin(n):
    if n == 0:
        return '0'
    ans = ''
    while n > 0:
        ans += str(n % 2)
        n //= 2
    return ''.join(ans[::-1])

def solve(n):
    arr = [[0 for _ in range(n)] for _ in range(n)]
    (low, high) = (1, n * n)
    f = True
    for i in range(n):
        for j in range(n):
            if f:
                f = False
                arr[i][j] = low
                low += 1
            else:
                f = True
                arr[i][j] = high
                high -= 1
        if i % 2:
            arr[i] = arr[i][::-1]
    ans = ''
    for a in arr:
        ans += ' '.join(list(map(str, a))) + '\n'
    return ans[:-1]

def main():
    t = in_int()
    for _ in range(t):
        n = in_int()
        print(solve(n))
if __name__ == '__main__':
    main()