Puzzle
Contest: Codeforces Round 802 (Div. 2)
Difficulty rating: 2600
Tags: constructive algorithms, dp, greedy

Pupils Alice and Ibragim are best friends. It's Ibragim's birthday soon, so Alice decided to gift him a new puzzle. The puzzle can be represented as a matrix with $$$2$$$ rows and $$$n$$$ columns, every element of which is either $$$0$$$ or $$$1$$$. In one move you can swap two values in neighboring cells.

More formally, let's number rows $$$1$$$ to $$$2$$$ from top to bottom, and columns $$$1$$$ to $$$n$$$ from left to right. Also, let's denote a cell in row $$$x$$$ and column $$$y$$$ as $$$(x, y)$$$. We consider cells $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ neighboring if $$$|x_1 - x_2| + |y_1 - y_2| = 1$$$.

Alice doesn't like the way in which the cells are currently arranged, so she came up with her own arrangement, with which she wants to gift the puzzle to Ibragim. Since you are her smartest friend, she asked you to help her find the minimal possible number of operations in which she can get the desired arrangement. Find this number, or determine that it's not possible to get the new arrangement.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — the number of columns in the puzzle.

Following two lines describe the current arrangement on the puzzle. Each line contains $$$n$$$ integers, every one of which is either $$$0$$$ or $$$1$$$.

The last two lines describe Alice's desired arrangement in the same format.

Output format:
If it is possible to get the desired arrangement, print the minimal possible number of steps, otherwise print $$$-1$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example the following sequence of swaps will suffice:

- $$$(2, 1), (1, 1)$$$,
- $$$(1, 2), (1, 3)$$$,
- $$$(2, 2), (2, 3)$$$,
- $$$(1, 4), (1, 5)$$$,
- $$$(2, 5), (2, 4)$$$.

It can be shown that $$$5$$$ is the minimal possible answer in this case.

In the second example no matter what swaps you do, you won't get the desired arrangement, so the answer is $$$-1$$$.

Example input:
5
0 1 0 1 0
1 1 0 0 1
1 0 1 0 1
0 0 1 1 0

Example output:
5

Example input:
3
1 0 0
0 0 0
0 0 0
0 0 0

Example output:
-1

Editorial:
We are asked to find a minimum cost perfect matching between $$$1$$$'s in the matrices, where the cost between $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is $$$|x_1 - x_2| + |y_1 - y_2|$$$. Notice that the answer exists only if the number of $$$1$$$'s is equal in both matrices. Consider that this is the case.
Notice that every $$$1$$$ either stays in its original row or changes it in a single operation. For simplicity let's assume that all operations of that kind are performed in the beginning. Let's denote $$$\Delta_{i,j}$$$ as the difference between the $$$j$$$-th prefix sum in $$$i$$$-th row of the matrices. If the final row for each $$$1$$$ is fixed, then the answer is equal to $$$S + \sum_{i=1}^n (|\Delta_{1,i}| + |\Delta_{2,i}|)$$$, where $$$S$$$ in the number of $$$1$$$'s that changed its row.
Now let's look at what happens when we change the row of a $$$1$$$. For simplicity let's assume that it was in a cell $$$(1, j)$$$. Then after the swap we have to increment $$$S$$$ by $$$1$$$, decrement all $$$\Delta_{1,j}, \dots \Delta_{1,n}$$$ by $$$1$$$, and increment all $$$\Delta_{2,j}, \dots \Delta_{2,n}$$$ by $$$1$$$.
Now let's solve the following problem: we are given $$$\Delta_{1,i}$$$ and $$$\Delta_{2,i}$$$ and in one operation we can increment some suffix by $$$1$$$ and decrement the same suffix in the other array by $$$1$$$. The goal is to minimize $$$S + \sum_{i=1}^n (|\Delta_{1,i}| + |\Delta_{2,i}|)$$$.
Notice that the following greedy algorithm works: iterate through columns from left to right and while $$$\Delta_{1,i}$$$ and $$$\Delta_{2,i}$$$ have different signs, decrement the suffix of one that's greater and increment suffix of one that's lower.
Now let's prove that this algorithm minimizes the target sum. For this consider some optimal sequence of operations. It doesn't matter in which order operations are performed, so let's assume they are performed from left to right, and are accumulated in a single element for the same suffix. If the sequences differ, denote $$$i$$$ as the first such position. Note that before that all $$$\Delta_{1,i}$$$ and $$$\Delta_{2,i}$$$ are the same in both our answer and the optimal one. Suppose that in the optimal answer we incremented $$$i$$$-th suffix of $$$\Delta_1$$$ by $$$k$$$ and decremented $$$i$$$-th suffix of $$$\Delta_2$$$ by $$$k$$$. Then the target sum will increase by $$$|k| + |\Delta_{1,i} + k| + |\Delta_{1,i} - k|$$$.
Consider the following cases:
• $$$\Delta_{1,i} \ge 0$$$ and $$$\Delta_{2,i} \ge 0$$$ or $$$\Delta_{1,i} \le 0$$$ and $$$\Delta_{2,i} \le 0$$$. By triangle inequality $$$|\Delta_{1,i} + k| + |\Delta_{2,i} - k| \ge |\Delta_{1,i} + \Delta_{2,i}| = |\Delta_{1,i}| + |\Delta_{2,i}|$$$, which means that those $$$k$$$ operations could be performed on the $$$i+1$$$-st suffix and that wouldn't increase the answer.
• $$$\Delta_{1,i} < 0$$$ and $$$\Delta_{2,i} > 0$$$. Here if $$$k < 0$$$, $$$|\Delta_{1,i} + k| + |\Delta_{2,i} - k| = 2|k| + |\Delta_{1,i}| + |\Delta_{2,i}|$$$, which means that those $$$k$$$ operations could be performed on the $$$i+1$$$-st suffix and that wouldn't increase the answer. Now if $$$k \ge 0$$$. We can assume that $$$k \le \min(-\Delta_{1,i}, \Delta_{2,i})$$$, otherwise we will perform an operation on values with the same sign, which we already shown can be done later on. Then $$$|k| + |\Delta_{1,i} + k| + |\Delta_{2,i} - k| = k + (-k - \Delta_{1,i}) + (\Delta_{2,i} - k) = -k - \Delta_{1,i} + \Delta_{2,i}$$$. Greedy algorithm suggests doing exactly $$$t = \min(-\Delta_{1,i}, \Delta_{2,i})$$$ operations. Note that if we perform $$$t$$$ operations on suffix $$$i$$$ and $$$t-k$$$ operations on suffix $$$i+1$$$, we will add $$$(-t - \Delta_{1,i} + \Delta_{2,i}) + (t - k) = -k - \Delta_{1,i} + \Delta_{2,i}$$$ to the answer and get the same state as the optimal answer. This means that we can do $$$t$$$ operations and not increase the answer.
• $$$\Delta_{1,i} > 0$$$ and $$$\Delta_{2,i} < 0$$$. This case can be analyzed in the same way.
Let's come back to the original problem. Described greedy algorithm finds a lower bound on the answer. Let's show that it is always possible to achieve it when the operations are allowed only for moving $$$1$$$'s between rows and the number of $$$1$$$s in each row at the end should be the same. For this note that we can "perform" operations on $$$1$$$'s from the second matrix, if we reverse their order and append to the end of the sequence for the first matrix. Now note that if on some prefix $$$i$$$ $$$\Delta_{1,i}$$$ and $$$\Delta_{2,i}$$$ have the same sign, but on prefix $$$i+1$$$ the signs differ, there has to be at least a single $$$1$$$ in column $$$i+1$$$, and we can perform the operation suggested by the greedy algorithm. Finally, if the answer exists it is true that $$$\Delta_{1,n} + \Delta_{2,n} = 0$$$, and if $$$\Delta_{1,n}$$$ and $$$\Delta_{2,n}$$$ have the same sign at the end this means that they are both $$$0$$$, which means that the constructed answer is correct.
This solution works in $$$O(n)$$$ time.