codeforces-scrape

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

1983B.md (3366B)


      1 Source: https://codeforces.com/problemset/problem/1983/B
      2 
      3 B. Corner Twist
      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 You are given two grids of numbers $a$ and $b$, with $n$ rows and $m$ columns. All the values in the grid are $0$, $1$ or $2$.
     22 
     23 You can perform the following operation on $a$ any number of times:
     24 
     25 * Pick any subrectangle in the grid with length and width $\ge 2$. You are allowed to choose the entire grid as a subrectangle.
     26 * The subrectangle has four corners. Take any pair of diagonally opposite corners of the chosen subrectangle and add $1$ to their values modulo $3$.
     27 * For the pair of corners not picked, add $2$ to their values modulo $3$.
     28 
     29 Note that the operation only changes the values of the corners of the picked subrectangle.
     30 
     31 Is it possible to convert the grid $a$ into grid $b$ by applying the above operation any number of times (possibly zero)?
     32 
     33 Input
     34 
     35 The first line contains an integer $t$, the number of testcases ($1 \le t \le 250$).
     36 
     37 For each testcase:
     38 
     39 The first line contains two integers $n$ and $m$, the number of rows and columns in the grid ($2 \le n,m \le 500$).
     40 
     41 Each of the next n lines contain m characters — the $j$-th character of the $i$-th line represents $a_{i,j}$.
     42 
     43 Each of the next n lines contain m characters — the $j$-th character of the $i$-th line represents $b_{i,j}$ ($0 \le a_{i,j}, b_{i,j} \le 2$).
     44 
     45 It is guaranteed that the sum of $n$ over all test cases and the sum of $m$ over all test cases do not exceed $500$.
     46 
     47 Output
     48 
     49 For each test case print "YES" (without quotes) if it is possible to convert grid $a$ into grid $b$ and "NO" (without quotes) otherwise.
     50 
     51 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 7
     59 
     60 3 3
     61 
     62 000
     63 
     64 000
     65 
     66 000
     67 
     68 111
     69 
     70 111
     71 
     72 111
     73 
     74 4 4
     75 
     76 0000
     77 
     78 0000
     79 
     80 0000
     81 
     82 0000
     83 
     84 2100
     85 
     86 1200
     87 
     88 0012
     89 
     90 0021
     91 
     92 4 4
     93 
     94 1020
     95 
     96 1200
     97 
     98 1210
     99 
    100 0000
    101 
    102 0000
    103 
    104 1200
    105 
    106 2200
    107 
    108 0000
    109 
    110 3 3
    111 
    112 012
    113 
    114 012
    115 
    116 012
    117 
    118 010
    119 
    120 111
    121 
    122 011
    123 
    124 8 8
    125 
    126 00000000
    127 
    128 00000000
    129 
    130 00000000
    131 
    132 00000000
    133 
    134 00000000
    135 
    136 00000000
    137 
    138 00000000
    139 
    140 10000000
    141 
    142 00000000
    143 
    144 01200000
    145 
    146 02010000
    147 
    148 00102000
    149 
    150 00020100
    151 
    152 00001020
    153 
    154 00000210
    155 
    156 10000000
    157 
    158 2 7
    159 
    160 0000000
    161 
    162 0000000
    163 
    164 2220111
    165 
    166 0111222
    167 
    168 2 7
    169 
    170 0000000
    171 
    172 0100010
    173 
    174 2220111
    175 
    176 1210202
    177 ```
    178 
    179 Output
    180 
    181 ```
    182 YES
    183 YES
    184 YES
    185 NO
    186 YES
    187 NO
    188 YES
    189 ```
    190 
    191 Note
    192 
    193 In the first testcase, grid $a$ can be converted into $b$ in the following manner:
    194 
    195 $\begin{matrix}\fbox{0} & 0 & \fbox{0}\\ 0 & 0 & 0\\ \fbox{0} & 0 & \fbox{0}\end{matrix} \Rightarrow \begin{matrix}1 & 0 & 2\\ 0 & \fbox{0} & \fbox{0}\\ 2 & \fbox{0} & \fbox{1}\end{matrix} \Rightarrow \begin{matrix}1 & 0 & 2\\ \fbox{0} & \fbox{1} & 2\\ \fbox{2} & \fbox{2} & 2\end{matrix} \Rightarrow \begin{matrix}1 & \fbox{0} & \fbox{2}\\ 1 & 0 & 2\\ 1 & \fbox{0} & \fbox{2}\end{matrix} \Rightarrow \begin{matrix}1 & 1 & 1\\ 1 & \fbox{0} & \fbox{2}\\ 1 & \fbox{2} & \fbox{0}\end{matrix} \Rightarrow \begin{matrix}1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{matrix}$
    196 
    197 Here, in each operation, the top-right and bottom-left corners highlighted by a box are incremented by $2$ modulo $3$, while the top-left and bottom-right corners are incremented by $1$ modulo $3$.
    198 
    199 In the fourth testcase, it can be proven that it is not possible to convert grid $a$ into grid $b$ using the above-mentioned operations any number of times.