codeforces-scrape

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

1980E.md (2874B)


      1 Source: https://codeforces.com/problemset/problem/1980/E
      2 
      3 E. Permutation of Rows and Columns
      4 
      5 time limit per test
      6 
      7 3 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 have been given a matrix $a$ of size $n$ by $m$, containing a permutation of integers from $1$ to $n \cdot m$.
     22 
     23 A permutation of $n$ integers is an array containing all numbers from $1$ to $n$ exactly once. For example, the arrays $[1]$, $[2, 1, 3]$, $[5, 4, 3, 2, 1]$ are permutations, while the arrays $[1, 1]$, $[100]$, $[1, 2, 4, 5]$ are not.
     24 
     25 A matrix contains a permutation if, when all its elements are written out, the resulting array is a permutation. Matrices $[[1, 2], [3, 4]]$, $[[1]]$, $[[1, 5, 3], [2, 6, 4]]$ contain permutations, while matrices $[[2]]$, $[[1, 1], [2, 2]]$, $[[1, 2], [100, 200]]$ do not.
     26 
     27 You can perform one of the following two actions in one operation:
     28 
     29 * choose columns $c$ and $d$ ($1 \le c, d \le m$, $c \ne d$) and swap these columns;
     30 * choose rows $c$ and $d$ ($1 \le c, d \le n$, $c \ne d$) and swap these rows.
     31 
     32 You can perform any number of operations.
     33 
     34 You are given the original matrix $a$ and the matrix $b$. Your task is to determine whether it is possible to transform matrix $a$ into matrix $b$ using the given operations.
     35 
     36 Input
     37 
     38 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The descriptions of the test cases follow.
     39 
     40 The first line of each test case description contains $2$ integers $n$ and $m$ ($1 \le n, m \le n \cdot m \le 2 \cdot 10^5$) — the sizes of the matrix.
     41 
     42 The next $n$ lines contain $m$ integers $a_{ij}$ each ($1 \le a_{ij} \le n \cdot m$). It is guaranteed that matrix $a$ is a permutation.
     43 
     44 The next $n$ lines contain $m$ integers $b_{ij}$ each ($1 \le b_{ij} \le n \cdot m$). It is guaranteed that matrix $b$ is a permutation.
     45 
     46 It is guaranteed that the sum of the values $n \cdot m$ for all test cases does not exceed $2 \cdot 10^5$.
     47 
     48 Output
     49 
     50 For each test case, output "YES" if the second matrix can be obtained from the first, and "NO" otherwise.
     51 
     52 You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.
     53 
     54 Example
     55 
     56 Input
     57 
     58 ```
     59 7
     60 
     61 1 1
     62 
     63 1
     64 
     65 1
     66 
     67 2 2
     68 
     69 1 2
     70 
     71 3 4
     72 
     73 4 3
     74 
     75 2 1
     76 
     77 2 2
     78 
     79 1 2
     80 
     81 3 4
     82 
     83 4 3
     84 
     85 1 2
     86 
     87 3 4
     88 
     89 1 5 9 6
     90 
     91 12 10 4 8
     92 
     93 7 11 3 2
     94 
     95 1 5 9 6
     96 
     97 12 10 4 8
     98 
     99 7 11 3 2
    100 
    101 3 3
    102 
    103 1 5 9
    104 
    105 6 4 2
    106 
    107 3 8 7
    108 
    109 9 5 1
    110 
    111 2 4 6
    112 
    113 7 8 3
    114 
    115 2 3
    116 
    117 1 2 6
    118 
    119 5 4 3
    120 
    121 6 1 2
    122 
    123 3 4 5
    124 
    125 1 5
    126 
    127 5 1 2 3 4
    128 
    129 4 2 5 1 3
    130 ```
    131 
    132 Output
    133 
    134 ```
    135 YES
    136 YES
    137 NO
    138 YES
    139 YES
    140 NO
    141 YES
    142 ```
    143 
    144 Note
    145 
    146 In the second example, the original matrix looks like this:
    147 
    148 $ \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} $
    149 
    150 By swapping rows $1$ and $2$, it becomes:
    151 
    152 $ \begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix} $
    153 
    154 By swapping columns $1$ and $2$, it becomes equal to matrix $b$:
    155 
    156 $ \begin{pmatrix} 4 & 3 \\ 2 & 1 \end{pmatrix} $