codeforces-scrape

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

2254C1.md (3288B)


      1 Source: https://codeforces.com/problemset/problem/2254/C1
      2 
      3 C1. Marenol (easy version)
      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 This is the easy version of the problem. In this version, you are only asked to determine whether string $a$ can be transformed into string $b$.
     22 
     23 Yousef has given you two binary strings, $a$ and $b$, of the same length $n$.
     24 
     25 You are allowed to perform any of the following operations:
     26 
     27 * Choose a substring$^{\text{∗}}$ in $a$ equal to $\texttt{001}$ and replace it with $\texttt{100}$, or vice versa (i.e., $\texttt{001} \rightarrow \texttt{100}$ or $\texttt{100} \rightarrow \texttt {001}$).
     28 * Choose a substring in $a$ equal to $\texttt{110}$ and replace it with $\texttt{011}$, or vice versa (i.e., $\texttt{011} \rightarrow \texttt{110}$ or $\texttt{110} \rightarrow \texttt {011}$).
     29 
     30 Your task is to determine whether it is possible to transform string $a$ into string $b$ using a finite number of operations.
     31 
     32 $^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly zero or all) characters from the beginning and several (possibly zero or all) characters from the end.
     33 
     34 Input
     35 
     36 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     37 
     38 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of each string.
     39 
     40 The second line of each test case contains a binary string $a$ ($|a| = n$), consisting of only characters $\texttt{0}$ and/or $\texttt{1}$.
     41 
     42 The third line of each test case contains a binary string $b$ ($|b| = n$), consisting of only characters $\texttt{0}$ and/or $\texttt{1}$.
     43 
     44 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     45 
     46 Output
     47 
     48 For each test case, output "YES" if the string $a$ can be transformed into string $b$ using a finite number of operations, and "NO" otherwise.
     49 
     50 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.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 9
     58 
     59 1
     60 
     61 0
     62 
     63 0
     64 
     65 2
     66 
     67 01
     68 
     69 10
     70 
     71 3
     72 
     73 001
     74 
     75 100
     76 
     77 4
     78 
     79 1010
     80 
     81 0101
     82 
     83 4
     84 
     85 1100
     86 
     87 1000
     88 
     89 5
     90 
     91 01001
     92 
     93 10010
     94 
     95 6
     96 
     97 110000
     98 
     99 000011
    100 
    101 6
    102 
    103 111000
    104 
    105 000111
    106 
    107 7
    108 
    109 1001100
    110 
    111 0000111
    112 ```
    113 
    114 Output
    115 
    116 ```
    117 YES
    118 
    119 NO
    120 
    121 YES
    122 
    123 NO
    124 
    125 NO
    126 
    127 YES
    128 
    129 YES
    130 
    131 NO
    132 
    133 YES
    134 ```
    135 
    136 Note
    137 
    138 In the first test case, it already holds that $a = b$. Therefore, the answer is YES.
    139 
    140 In the second test case, we cannot perform any operation. Since $a \neq b$, the answer is NO.
    141 
    142 In the third test case, we can choose the substring $a[1, 3] = \texttt{001}$ and replace it with $\texttt{100}$, making $a = b$. Therefore, the answer is YES.
    143 
    144 In the seventh test case, we can do the following in order:
    145 
    146 * $\texttt{1}$${\color{blue}{\texttt{100}}}$$\texttt{00}$ $\rightarrow$ $\texttt{1}$${\color{blue}{\texttt{001}}}$$\texttt{00}$
    147 * $\texttt{100}$${\color{blue}{\texttt{100}}}$ $\rightarrow$ $\texttt{100}$${\color{blue}{\texttt{001}}}$
    148 * ${\color{blue}{\texttt{100}}}$$\texttt{001}$ $\rightarrow$ ${\color{blue}{\texttt{001}}}$$\texttt{001}$
    149 * $\texttt{00}$${\color{blue}{\texttt{100}}}$$\texttt{1}$ $\rightarrow$ $\texttt{00}$${\color{blue}{\texttt{001}}}$$\texttt{1}$
    150 
    151 Therefore, the answer is YES.