Moving Chips
Contest: Educational Codeforces Round 128 (Rated for Div. 2)
Difficulty rating: 2000
Tags: bitmasks, dp, greedy

You are given a board of size $$$2 \times n$$$ ($$$2$$$ rows, $$$n$$$ columns). Some cells of the board contain chips. The chip is represented as '*', and an empty space is represented as '.'. It is guaranteed that there is at least one chip on the board.

In one move, you can choose any chip and move it to any adjacent (by side) cell of the board (if this cell is inside the board). It means that if the chip is in the first row, you can move it left, right or down (but it shouldn't leave the board). Same, if the chip is in the second row, you can move it left, right or up.

If the chip moves to the cell with another chip, the chip in the destination cell disappears (i. e. our chip captures it).

Your task is to calculate the minimum number of moves required to leave exactly one chip on the board.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the board. The second line of the test case contains the string $$$s_1$$$ consisting of $$$n$$$ characters '*' (chip) and/or '.' (empty cell). The third line of the test case contains the string $$$s_2$$$ consisting of $$$n$$$ characters '*' (chip) and/or '.' (empty cell).

Additional constraints on the input:

- in each test case, there is at least one chip on a board;
- the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output format:
For each test case, print one integer — the minimum number of moves required to leave exactly one chip on the board.

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

Example input:
5
1
*
.
2
.*
**
3
*.*
.*.
4
**.*
**..
5
**...
...**

Example output:
0
2
3
5
5

Editorial:
Firstly, I want to say a few words about the difficulty of this problem. Till the last moment, we didn't know easy to prove (and easy to write) solutions, so we decided that this is a good problem E. But now we realized it is a lot easier than we expected.
Now, let's talk about the solution. At the beginning, let's remove redundant columns from the beginning and from the end (i. e. columns without chips) and change the value $$$n$$$ correspondingly. Now, let $$$cost_{i, j}$$$ be $$$1$$$ if $$$s_{j, i}$$$ is '*', and $$$0$$$ otherwise. This array needed to make the implementation easier.
Let's calculate the dynamic programming $$$dp_{i, j}$$$, where $$$i$$$ is the index of the last processed column and $$$j$$$ is the number of the row where our chip is standing. This seems a bit suspicious why we can calculate such a dynamic programming, so let's explain some things about it.
• It can be shown that in the optimal answer there will be some column where the last move happens. And if the number of this column is $$$j$$$ then all chips to the left of $$$j$$$ will move only to the right and all chips to the right of $$$j$$$ will move only to the left.
• Actually, we can always consider that $$$j$$$ is the last column. Consider paths of two chips that will survive till the last move. The first chip is to the left of $$$j$$$ and will move only to the right, and the second one is to the right of $$$j$$$ and will move only to the left. Then we can replicate the path of the second chip in the reverse order using the first chip. So the second chip can stay still until the last move.
• In the optimal answer, it is always better to have exactly one chip in the current column, because moving two chips to the right is always worse than just eat one of them and move the remaining one.
Initial states of $$$dp$$$ are $$$+\infty$$$ except the values of the first column. For the first column, $$$dp_{0, 0} = cost_{0, 1}$$$ and $$$dp_{0, 1} = cost_{0, 0}$$$. The answer will be $$$min(dp_{n - 1, 0}, dp_{n - 1, 1})$$$.
Okay, how to make transitions from $$$dp_{i, j}$$$? For all $$$i$$$ from $$$0$$$ to $$$n-2$$$, let's consider four cases:
• $$$dp_{i, 0} \rightarrow dp_{i + 1, 0}$$$ — here we need one move to go to the next column and, probably, one more move to delete the figure in the second row in the column $$$i + 1$$$. So the transition seems like $$$dp_{i + 1, 0} = min(dp_{i + 1, 0}, dp_{i, 0} + 1 + cost_{i + 1, 1})$$$;
• $$$dp_{i, 1} \rightarrow dp_{i + 1, 1}$$$ — same as the previous transition, $$$dp_{i + 1, 1} = min(dp_{i + 1, 1}, dp_{i, 1} + 1 + cost_{i + 1, 0})$$$;
• $$$dp_{i, 0} \rightarrow dp_{i + 1, 1}$$$ — because the cost of this transition is always $$$2$$$ (the distance between these cells is $$$2$$$), we just go firstly to the right and then down (to ensure that we eat the figure in the first row). So the transition is $$$dp_{i + 1, 1} = min(dp_{i + 1, 1}, dp_{i, 0} + 2)$$$;
• $$$dp_{i, 1} \rightarrow dp_{i + 1, 1}$$$ — same as the previous transition, $$$dp_{i + 1, 0} = min(dp_{i + 1, 0}, dp_{i, 1} + 2)$$$.
Time complexity: $$$O(n)$$$.