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.