1136C.md (3000B)
1 Source: https://codeforces.com/problemset/problem/1136/C 2 3 C. Nastya Is Transposing Matrices 4 5 time limit per test 6 7 1 second 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 Nastya came to her informatics lesson, and her teacher who is, by the way, a little bit famous here gave her the following task. 22 23 Two matrices $A$ and $B$ are given, each of them has size $n \times m$. Nastya can perform the following operation to matrix $A$ unlimited number of times: 24 25 * take any square square submatrix of $A$ and transpose it (i.e. the element of the submatrix which was in the $i$-th row and $j$-th column of the submatrix will be in the $j$-th row and $i$-th column after transposing, and the transposed submatrix itself will keep its place in the matrix $A$). 26 27 Nastya's task is to check whether it is possible to transform the matrix $A$ to the matrix $B$. 28 29  Example of the operation 30 31 As it may require a lot of operations, you are asked to answer this question for Nastya. 32 33 A square submatrix of matrix $M$ is a matrix which consist of all elements which comes from one of the rows with indeces $x, x+1, \dots, x+k-1$ of matrix $M$ and comes from one of the columns with indeces $y, y+1, \dots, y+k-1$ of matrix $M$. $k$ is the size of square submatrix. In other words, square submatrix is the set of elements of source matrix which form a solid square (i.e. without holes). 34 35 Input 36 37 The first line contains two integers $n$ and $m$ separated by space ($1 \leq n, m \leq 500$) — the numbers of rows and columns in $A$ and $B$ respectively. 38 39 Each of the next $n$ lines contains $m$ integers, the $j$-th number in the $i$-th of these lines denotes the $j$-th element of the $i$-th row of the matrix $A$ ($1 \leq A_{ij} \leq 10^{9}$). 40 41 Each of the next $n$ lines contains $m$ integers, the $j$-th number in the $i$-th of these lines denotes the $j$-th element of the $i$-th row of the matrix $B$ ($1 \leq B_{ij} \leq 10^{9}$). 42 43 Output 44 45 Print "YES" (without quotes) if it is possible to transform $A$ to $B$ and "NO" (without quotes) otherwise. 46 47 You can print each letter in any case (upper or lower). 48 49 Examples 50 51 Input 52 53 ``` 54 2 2 55 1 1 56 6 1 57 1 6 58 1 1 59 ``` 60 61 Output 62 63 ``` 64 YES 65 ``` 66 67 Input 68 69 ``` 70 2 2 71 4 4 72 4 5 73 5 4 74 4 4 75 ``` 76 77 Output 78 79 ``` 80 NO 81 ``` 82 83 Input 84 85 ``` 86 3 3 87 1 2 3 88 4 5 6 89 7 8 9 90 1 4 7 91 2 5 6 92 3 8 9 93 ``` 94 95 Output 96 97 ``` 98 YES 99 ``` 100 101 Note 102 103 Consider the third example. The matrix $A$ initially looks as follows. 104 105 $$ \begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{bmatrix} $$ 106 107 Then we choose the whole matrix as transposed submatrix and it becomes 108 109 $$ \begin{bmatrix} 1 & 4 & 7\\ 2 & 5 & 8\\ 3 & 6 & 9 \end{bmatrix} $$ 110 111 Then we transpose the submatrix with corners in cells $(2, 2)$ and $(3, 3)$. 112 113 $$ \begin{bmatrix} 1 & 4 & 7\\ 2 & \textbf{5} & \textbf{8}\\ 3 & \textbf{6} & \textbf{9} \end{bmatrix} $$ 114 115 So matrix becomes 116 117 $$ \begin{bmatrix} 1 & 4 & 7\\ 2 & 5 & 6\\ 3 & 8 & 9 \end{bmatrix} $$ 118 119 and it is $B$.