201191: [AtCoder]ARC119 B - Electric Board
Description
Score: $500$ points
Problem Statement
An electric bulletin board is showing a string $S$ of length $N$ consisting of 0
and 1
.
You can do the following operation any number of times, where $S_i$ denotes the $i$-th character $(1 \leq i \leq N)$ of the string shown in the board.
Operation: choose a pair of integers $(l, r)$ $(1 \leq l < r \leq N)$ satisfying one of the conditions below, and swap $S_l$ and $S_r$.
- $S_l=$
0
and $S_{l+1}=\cdots=S_r=$1
.- $S_{l}=\cdots=S_{r-1}=$
1
and $S_r=$0
.
Determine whether it is possible to make the string shown in the board match $T$, and find the minimum number of operations needed if it is possible.
Constraints
- $2 \leq N \leq 500000$
- $S$ is a string of length $N$ consisting of
0
and1
. - $T$ is a string of length $N$ consisting of
0
and1
.
Input
Input is given from Standard Input in the following format:
$N$ $S$ $T$
Output
If it is impossible to make the board show the string $T$, print -1
.
If it is possible, find the minimum number of operations needed.
Sample Input 1
7 1110110 1010111
Sample Output 1
2
Here is one possible way to make the board show the string 1010111
in two operations:
- Do the operation with $(l, r) = (2, 4)$, changing the string in the board from
1110110
to1011110
. - Do the operation with $(l, r) = (4, 7)$, changing the string in the board from
1011110
to1010111
.
Sample Input 2
20 11111000000000011111 11111000000000011111
Sample Output 2
0
The board already shows the string $T$ before doing any operation, so the answer is $0$.
Sample Input 3
6 111100 111000
Sample Output 3
-1
If there is no sequence of operations that makes the board show the string $T$, print -1
.
Sample Input 4
119 10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011 11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011
Sample Output 4
22