codeforces-scrape

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

2101A.md (2126B)


      1 Source: https://codeforces.com/problemset/problem/2101/A
      2 
      3 A. Mex in the Grid
      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 You are given $n^2$ cards with values from $0$ to $n^2-1$. You are to arrange them in a $n$ by $n$ grid such that there is exactly one card in each cell.
     22 
     23 The MEX (minimum excluded value) of a subgrid$^{\text{∗}}$ is defined as the smallest non-negative integer that does not appear in the subgrid.
     24 
     25 Your task is to arrange the cards such that the sum of MEX values over all $\left(\frac{n(n+1)}{2}\right)^2$ subgrids is maximized.
     26 
     27 $^{\text{∗}}$A subgrid of a $n$ by $n$ grid is specified by four numbers $l_1, r_1, l_2, r_2$ satisfying $1\le l_1\le r_1\le n$ and $1\le l_2\le r_2\le n$. The element in the $i$-th row and the $j$-th column of the grid is part of the subgrid if and only if $l_1\le i\le r_1$ and $l_2\le j\le r_2$.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.
     32 
     33 The first line of each test case contains a single integer $n$ ($1\le n\le 500$) — the side length of the grid.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.
     36 
     37 Output
     38 
     39 For each test case, output $n$ lines, each containing $n$ integers representing the elements of the grid.
     40 
     41 If there are multiple answers, you can output any of them.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 2
     49 
     50 2
     51 
     52 3
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 0 1 
     59 2 3 
     60 8 4 5 
     61 6 0 1 
     62 7 2 3
     63 ```
     64 
     65 Note
     66 
     67 In the first test case, one valid arrangement is:
     68 
     69 |  |  |
     70 | --- | --- |
     71 | 0 | 1 |
     72 | 2 | 3 |
     73 
     74 There are $9$ subgrids in total, and the $4$ of them with non-zero MEX are shown below:
     75 
     76 |  |
     77 | --- |
     78 | 0 |
     79 
     80 values:$[0]$ — MEX: $1$
     81 
     82 |  |  |
     83 | --- | --- |
     84 | 0 | 1 |
     85 
     86 values:$[0, 1]$  — MEX: $2$
     87 
     88 |  |
     89 | --- |
     90 | 0 |
     91 | 2 |
     92 
     93 values:$[0, 2]$  — MEX: $1$
     94 
     95 |  |  |
     96 | --- | --- |
     97 | 0 | 1 |
     98 | 2 | 3 |
     99 
    100 values:$[0, 1, 2, 3]$  — MEX: $4$
    101 
    102 The sum of MEX over all subgrids would be $1+2+1+4 = 8$. It can be proven that no other arrangements have a larger sum of MEX values.