Cleaning Robot
Contest: Educational Codeforces Round 136 (Rated for Div. 2)
Difficulty rating: 2400
Tags: bitmasks, dp

Consider a hallway, which can be represented as the matrix with $$$2$$$ rows and $$$n$$$ columns. Let's denote the cell on the intersection of the $$$i$$$-th row and the $$$j$$$-th column as $$$(i, j)$$$. The distance between the cells $$$(i_1, j_1)$$$ and $$$(i_2, j_2)$$$ is $$$|i_1 - i_2| + |j_1 - j_2|$$$.

There is a cleaning robot in the cell $$$(1, 1)$$$. Some cells of the hallway are clean, other cells are dirty (the cell with the robot is clean). You want to clean the hallway, so you are going to launch the robot to do this.

After the robot is launched, it works as follows. While at least one cell is dirty, the robot chooses the closest (to its current cell) cell among those which are dirty, moves there and cleans it (so the cell is no longer dirty). After cleaning a cell, the robot again finds the closest dirty cell to its current cell, and so on. This process repeats until the whole hallway is clean.

However, there is a critical bug in the robot's program. If at some moment, there are multiple closest (to the robot's current position) dirty cells, the robot malfunctions.

You want to clean the hallway in such a way that the robot doesn't malfunction. Before launching the robot, you can clean some (possibly zero) of the dirty cells yourself. However, you don't want to do too much dirty work yourself while you have this nice, smart (yet buggy) robot to do this. Note that you cannot make a clean cell dirty.

Calculate the maximum possible number of cells you can leave dirty before launching the robot, so that it doesn't malfunction.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of columns in the hallway.

Then two lines follow, denoting the $$$1$$$-st and the $$$2$$$-nd row of the hallway. These lines contain $$$n$$$ characters each, where 0 denotes a clean cell and 1 denotes a dirty cell. The starting cell of the robot $$$(1, 1)$$$ is clean.

Output format:
Print one integer — the maximum possible number of cells you can leave dirty before launching the robot, so that it doesn't malfunction.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first example, you can clean the cell $$$(1, 2)$$$, so the path of the robot is $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$$$.

In the second example, you can leave the hallway as it is, so the path of the robot is $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$$$.

In the third example, you can clean the cell $$$(1, 2)$$$, so the path of the robot is $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4)$$$.

In the fourth example, the hallway is already clean. Maybe you have launched the robot earlier?

Example input:
2
01
11

Example output:
2

Example input:
2
01
01

Example output:
2

Editorial:
Why did the author choose the width of the hallway to be only $$$2$$$? Well, in that case you can show that the robot will never move to the left while cleaning. That is not true on width $$$3$$$ already.
When does the robot break? Let the robot currently be in the cell $$$(j, i)$$$ ($$$0$$$-indexed) and the next column with a dirty cell be $$$\mathit{nxt}_i$$$ (possibly, $$$\mathit{nxt}_i = i$$$). The robot breaks only if both $$$(1 - j, \mathit{nxt}_i)$$$ and $$$(j, \mathit{nxt}_i)$$$ are dirty.
That helps us to do a dynamic programming solution. Since we can only care about $$$O(1)$$$ next columns, we would want to have some $$$dp[i][j]$$$ — the largest number of dirty cells we can leave to the robot if we processed the first $$$i$$$ columns of the hallway and are currently standing in the $$$j$$$-th row of the $$$i$$$-th column. Maybe with some additional states of the current or the next columns.
We want the dp to maintain the invariant that everything to the left of the $$$i$$$-th column is cleaned in such a way the robot can reach the cell $$$(j, i)$$$. We can choose when to fix the $$$i$$$-th column: either maintain it being correct prior to entering the state or handling it in the transition to the next one. I chose the former option. There probably exists a million different dps that work, I'll describe the one I did.
Let $$$dp[i][j][f]$$$ be the largest number of dirty cells that we can leave to the robot if:
• we fixed which of the dirty cells in the first $$$i$$$ columns, inclusive, are cleaned by hand;
• the robot reaches the cell $$$(j, i)$$$ from the left;
• $$$f$$$ is true if the cell in the opposite row of the $$$i$$$-th column is dirty.
The transitions handle what to do with the dirty cells in the $$$(i+1)$$$-st column and where the robot goes based on that.
In particular, there are the following transitions:
• if $$$f$$$ is true, then we have to clean the cell $$$(j, i + 1)$$$, and the robot will move into $$$(1 - j, i + 1)$$$ — otherwise the robot breaks from having two options;
• if $$$f$$$ is false, then let's say that the robot doesn't break immediately but moves into the next column in a unique way: it moves horizontally first, then possibly vertically;   we can leave the next column as is, and the robot will move into $$$(j, i + 1)$$$ if the cell $$$(1 - j, i + 1)$$$ is clean, or $$$(1 - j, i + 1)$$$ if it's dirty;   if $$$f$$$ is false, then we can clean the cell $$$(1 - j, i + 1)$$$, and the robot will move into $$$(j, i + 1)$$$.
• we can leave the next column as is, and the robot will move into $$$(j, i + 1)$$$ if the cell $$$(1 - j, i + 1)$$$ is clean, or $$$(1 - j, i + 1)$$$ if it's dirty;
• if $$$f$$$ is false, then we can clean the cell $$$(1 - j, i + 1)$$$, and the robot will move into $$$(j, i + 1)$$$.
Since we maintained the invariant that the $$$i$$$-th column is valid, we can update the answer from all four states in the last column.
Overall complexity: $$$O(n)$$$.