codeforces-scrape

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

2254C2.md (3072B)


      1 Source: https://codeforces.com/problemset/problem/2254/C2
      2 
      3 C2. Marenol (hard 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 hard version of the problem. In this version, you are asked to determine the minimum number of operations to transform $a$ into $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 the minimum number of operations required to transform string $a$ into string $b$. If it is impossible to transform $a$ into $b$ using the given operations, output $-1$ instead.
     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 the minimum number of operations required to transform $a$ into $b$. If it is impossible, output $-1$ instead.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 5
     56 
     57 4
     58 
     59 0100
     60 
     61 0001
     62 
     63 4
     64 
     65 0100
     66 
     67 0010
     68 
     69 6
     70 
     71 110000
     72 
     73 000011
     74 
     75 8
     76 
     77 10101010
     78 
     79 10101010
     80 
     81 5
     82 
     83 01001
     84 
     85 10010
     86 ```
     87 
     88 Output
     89 
     90 ```
     91 1
     92 
     93 -1
     94 
     95 4
     96 
     97 0
     98 
     99 3
    100 ```
    101 
    102 Note
    103 
    104 In the first test case, we can choose the substring $a[2, 4] = \texttt{100}$ and replace it with $\texttt{001}$. This takes exactly $1$ operation.
    105 
    106 In the second test case, it is impossible to transform $a$ into $b$, so the answer is $-1$.
    107 
    108 In the third test case, we can do the following in order:
    109 
    110 * $\texttt{1}$${\color{blue}{\texttt{100}}}$$\texttt{00}$ $\rightarrow$ $\texttt{1}$${\color{blue}{\texttt{001}}}$$\texttt{00}$
    111 * $\texttt{100}$${\color{blue}{\texttt{100}}}$ $\rightarrow$ $\texttt{100}$${\color{blue}{\texttt{001}}}$
    112 * ${\color{blue}{\texttt{100}}}$$\texttt{001}$ $\rightarrow$ ${\color{blue}{\texttt{001}}}$$\texttt{001}$
    113 * $\texttt{00}$${\color{blue}{\texttt{100}}}$$\texttt{1}$ $\rightarrow$ $\texttt{00}$${\color{blue}{\texttt{001}}}$$\texttt{1}$
    114 
    115 This takes $4$ operations. It can be shown that $4$ is the minimum answer.