codeforces-scrape

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

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  ![](https://espresso.codeforces.com/0ed105b4ebafba868ce325a5141bddf779ecb9f0.png) 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$.