codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1956C.md (3093B)


      1 Source: https://codeforces.com/problemset/problem/1956/C
      2 
      3 C. Nene's Magical Matrix
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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}$.
     22 
     23 She can perform operations of the following two types with this matrix:
     24 
     25 * 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.
     26 * 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.
     27 
     28 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.
     29 
     30 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).
     31 
     32 Input
     33 
     34 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.
     35 
     36 The only line of each test case contains a single integer $n$ ($1 \le n \le 500$) — the size of the matrix $a$.
     37 
     38 It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5 \cdot 10^5$.
     39 
     40 Output
     41 
     42 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.
     43 
     44 In the $k$-th of the next $m$ lines output the description of the $k$-th operation:
     45 
     46 * an integer $c$ ($c \in \{1, 2\}$) — the type of the $k$-th operation;
     47 * an integer $i$ ($1 \le i \le n$) — the row or the column the $k$-th operation is applied to;
     48 * a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ — the permutation used in the $k$-th operation.
     49 
     50 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.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 2
     58 
     59 1
     60 
     61 2
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 1 1
     68 
     69 1 1 1
     70 
     71 7 3
     72 
     73 1 1 1 2
     74 
     75 1 2 1 2
     76 
     77 2 1 1 2
     78 ```
     79 
     80 Note
     81 
     82 In the first test case, the maximum sum $s=1$ can be obtained in $1$ operation by setting $a_{1, 1}:=1$.
     83 
     84 In the second test case, the maximum sum $s=7$ can be obtained in $3$ operations as follows:
     85 
     86  ![](https://espresso.codeforces.com/53c36219aeab609218b3b2c206283e7998417968.png) 
     87 
     88 It can be shown that it is impossible to make the sum of the numbers in the matrix larger than $7$.