Nene's Magical Matrix
Contest: Codeforces Round 939 (Div. 2)
Difficulty rating: 1600
Tags: constructive algorithms, greedy, math

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
2
1
2

Example output:
1 1
1 1 1
7 3
1 1 1 2
1 2 1 2
2 1 1 2

Editorial:
Hint
When $$$n=3$$$, the optimal matrix is the following:
Solution
The optimal matrix would be:
Construction method:
This takes exactly $$$2n$$$ operations.
Proof
For the final matrix, we define $$$f(x)$$$ as the number of elements greater or equal to $$$x$$$. The sum of all elements in the matrix is $$$\sum_{i=1}^n f(i)$$$ because an element with value $$$x$$$ will be counted $$$x$$$ times in the formula before.
Now, we proof that $$$f(x) \le n^2-(x-1)^2$$$:
Let's rewrite the problem to make it a little simpler:
• You have an $$$n\times n$$$ matrix. In each operation, you can paint exactly $$$x-1$$$ cells white and $$$n-(x-1)$$$ cells black in a row or a column. Proof that there will be at most $$$n^2-(x-1)^2$$$ black cells.
Try to strengthen the conclusion by stating that:
• For any matrix of size $$$n\times m$$$, each operation can paint a row into $$$x$$$ white cells and $$$m-x$$$ black cells, or a column into $$$y$$$ white cells and $$$n-y$$$ black cells. No matter how we paint, the final matrix will have at most $$$nm-xy$$$ black cells.
We will prove this by induction.
If $$$x=n$$$ or $$$y=m$$$, the conclusion holds.
Otherwise, if the last operation is to paint a row, then this row has exactly $$$m-x$$$ black cells. And, by induction, other rows will contain at most $$$(n-1)m-x(y-1)$$$ black cells. Painting a column in the last step is similar.
Then, we have proven the conclusion above.
Since the construction above maximizes each $$$f(x)$$$, it is the optimal answer.