Nene's Magical Matrix (Codeforces 1956C)
Tags: Greedy, constructive algorithms

The magical girl Nene has an $$$n\times n$$$ matrix $$$a$$$ filled with zeroes. The $$$j$$$-th element of the $$$i$$$-th row of matrix $$$a$$$ is denoted as $$$a_{i, j}$$$.She can perform operations of the following two types with this matrix:  Type $$$1$$$ operation: choose an integer $$$i$$$ between $$$1$$$ and $$$n$$$ and a permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$. Assign $$$a_{i, j}:=p_j$$$ for all $$$1 \le j \le n$$$ simultaneously.  Type $$$2$$$ operation: choose an integer $$$i$$$ between $$$1$$$ and $$$n$$$ and a permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$. Assign $$$a_{j, i}:=p_j$$$ for all $$$1 \le j \le n$$$ simultaneously. Nene wants to maximize the sum of all the numbers in the matrix $$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$$$. She asks you to find the way to perform the operations so that this sum is maximized. As she doesn't want to make too many operations, you should provide a solution with no more than $$$2n$$$ operations.A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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 test cases follows.The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 500$$$) — the size of the matrix $$$a$$$.It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output: For each test case, in the first line output two integers $$$s$$$ and $$$m$$$ ($$$0\leq m\leq 2n$$$) — the maximum sum of the numbers in the matrix and the number of operations in your solution.In the $$$k$$$-th of the next $$$m$$$ lines output the description of the $$$k$$$-th operation:   an integer $$$c$$$ ($$$c \in \{1, 2\}$$$) — the type of the $$$k$$$-th operation;  an integer $$$i$$$ ($$$1 \le i \le n$$$) — the row or the column the $$$k$$$-th operation is applied to;  a permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$ — the permutation used in the $$$k$$$-th operation. Note that you don't need to minimize the number of operations used, you only should use no more than $$$2n$$$ operations. It can be shown that the maximum possible sum can always be obtained in no more than $$$2n$$$ operations.

Note: In the first test case, the maximum sum $$$s=1$$$ can be obtained in $$$1$$$ operation by setting $$$a_{1, 1}:=1$$$.In the second test case, the maximum sum $$$s=7$$$ can be obtained in $$$3$$$ operations as follows:  It can be shown that it is impossible to make the sum of the numbers in the matrix larger than $$$7$$$.

Sample Inputs:
2
1
2

Sample Outputs:
1 1
1 1 1
7 3
1 1 1 2
1 2 1 2
2 1 1 2

Solution (Python):
def other_solution():
    n = int(input())
    sum = int(n * (n + 1) * (2 * n + 1) / 3 - n * (n + 1) / 2)
    print(sum, 2 * n)
    r = ''
    for j in range(1, n + 1):
        r += str(j) + ' '
    r = r[:-1]
    for i in range(1, n + 1):
        print(1, n - i + 1, r)
        print(2, n - i + 1, r)
if __name__ == '__main__':
    t = int(input())
    while t:
        t -= 1
        other_solution()

Solution (Python):
T = int(input())
for _ in range(0, T):
    n = int(input())
    l = [str(i) for i in range(1, n + 1)]
    l = ' '.join(l)
    sm = n * (n + 1) * (2 * n + 1) // 3 - n * (n + 1) // 2
    print(sm, 2 * n - 1)
    s = '2 ' + str(n) + ' ' + l
    print(s)
    for i in range(n - 1, 0, -1):
        s = str(i) + ' ' + l
        print(1, s)
        print(2, s)

Solution (Python):
T = int(input())
import math
for t in range(T):
    n = int(input())
    suma = 0
    for i in range(1, n + 1):
        suma += n ** 2 - (i - 1) ** 2
    print(suma, 2 * n)
    r = ''
    for j in range(1, n + 1):
        r += str(j) + ' '
    r = r[:-1]
    pos = len(r) - 1
    for i in range(1, n + 1):
        print(1, n - i + 1, r)
        print(2, n - i + 1, r)