codeforces-scrape

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

1868A.md (2862B)


      1 Source: https://codeforces.com/problemset/problem/1868/A
      2 
      3 A. Fill in the 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 There is an empty matrix $M$ of size $n\times m$.
     22 
     23 Zhongkao examination is over, and Daniel would like to do some puzzle games. He is going to fill in the matrix $M$ using permutations of length $m$. That is, each row of $M$ must be a permutation of length $m^\dagger$.
     24 
     25 Define the value of the $i$-th column in $M$ as $v_i=\operatorname{MEX}(M_{1,i},M_{2,i},\ldots,M_{n,i})^\ddagger$. Since Daniel likes diversity, the beauty of $M$ is $s=\operatorname{MEX}(v_1,v_2,\cdots,v_m)$.
     26 
     27 You have to help Daniel fill in the matrix $M$ and maximize its beauty.
     28 
     29 $^\dagger$ A permutation of length $m$ is an array consisting of $m$ distinct integers from $0$ to $m-1$ in arbitrary order. For example, $[1,2,0,4,3]$ is a permutation, but $[0,1,1]$ is not a permutation ($1$ appears twice in the array), and $[0,1,3]$ is also not a permutation ($m-1=2$ but there is $3$ in the array).
     30 
     31 $^\ddagger$ The $\operatorname{MEX}$ of an array is the smallest non-negative integer that does not belong to the array. For example, $\operatorname{MEX}(2,2,1)=0$ because $0$ does not belong to the array, and $\operatorname{MEX}(0,3,1,2)=4$ because $0$, $1$, $2$ and $3$ appear in the array, but $4$ does not.
     32 
     33 Input
     34 
     35 The first line of input contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases. The description of test cases follows.
     36 
     37 The only line of each test case contains two integers $n$ and $m$ ($1\le n,m\le 2\cdot 10^5$) — the size of the matrix.
     38 
     39 It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $2\cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, in the first line output a single integer — the maximum beauty of $M$.
     44 
     45 Then output the matrix $M$ of size $n\times m$ — the matrix you find.
     46 
     47 If there are multiple solutions, you may output any of them.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 4
     55 
     56 4 3
     57 
     58 1 16
     59 
     60 6 6
     61 
     62 2 1
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 3
     69 1 0 2
     70 0 2 1
     71 1 0 2
     72 0 2 1
     73 2
     74 14 7 15 4 10 0 8 6 1 2 3 5 9 11 12 13 
     75 6
     76 3 0 1 4 2 5 
     77 5 2 1 0 4 3 
     78 1 3 2 4 5 0 
     79 4 1 3 2 5 0 
     80 4 2 5 3 0 1 
     81 2 4 0 5 1 3
     82 0
     83 0
     84 0
     85 ```
     86 
     87 Note
     88 
     89 In the first test case:
     90 
     91 * $v_1=\operatorname{MEX}(1,0,1,0)=2$;
     92 * $v_2=\operatorname{MEX}(0,2,0,2)=1$;
     93 * $v_3=\operatorname{MEX}(2,1,2,1)=0$.
     94 
     95 Therefore, $s=\operatorname{MEX}(2,1,0)=3$.
     96 
     97 It can be shown that $3$ is the maximum possible beauty of $M$.
     98 
     99 In the second test case, any permutation will make $s=2$.
    100 
    101 In the third test case:
    102 
    103 * $v_1=\operatorname{MEX}(3,5,1,4,4,2)=0$;
    104 * $v_2=\operatorname{MEX}(0,2,3,1,2,4)=5$;
    105 * $v_3=\operatorname{MEX}(1,1,2,3,5,0)=4$;
    106 * $v_4=\operatorname{MEX}(4,0,4,2,3,5)=1$;
    107 * $v_5=\operatorname{MEX}(2,4,5,5,0,1)=3$;
    108 * $v_6=\operatorname{MEX}(5,3,0,0,1,3)=2$.
    109 
    110 Therefore, $s=\operatorname{MEX}(0,5,4,1,3,2)=6$.