Cleaning Robot (Codeforces 1739E)
Tags: DP, bitmasks

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: 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: Print one integer — the maximum possible number of cells you can leave dirty before launching the robot, so that it doesn't malfunction.

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?

Sample Inputs:
2
01
11

2
01
01

4
0101
1011

4
0000
0000

5
00011
10101

6
011111
111111

10
0101001010
1010100110

Sample Outputs:
2

2

4

0

4

8

6

Solution (Python):
from math import inf
n = int(input())
row_1 = list(map(int, input()))
row_2 = list(map(int, input()))
hall = [row_1, row_2]
dp = [[[-inf, -inf] for i in range(2)] for i in range(n)]
dp[0][0][0] = 0
dp[0][0][hall[1][0]] = hall[1][0]
for i in range(n - 1):
    for j in range(2):
        next_hor = hall[j][i + 1]
        next_diag = hall[j ^ 1][i + 1]
        dp[i + 1][j][next_diag] = max(dp[i + 1][j][next_diag], dp[i][j][0] + next_hor + next_diag)
        dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][0] + next_hor)
        dp[i + 1][j ^ 1][0] = max(dp[i + 1][j ^ 1][0], dp[i][j][1] + next_diag)
print(max([dp[n - 1][0][1], dp[n - 1][0][0], dp[n - 1][1][1], dp[n - 1][1][0]]))

Solution (Python):
from math import inf
n = int(input())
row_1 = list(map(int, input()))
row_2 = list(map(int, input()))
hall = [row_1, row_2]
dp = [[[-inf, -inf] for i in range(2)] for i in range(n + 1)]
dp[0][0][0] = 0
dp[0][0][hall[1][0]] = hall[1][0]
for i in range(n - 1):
    for j in range(2):
        next_hor = hall[j][i + 1]
        next_diag = hall[j ^ 1][i + 1]
        dp[i + 1][j][next_diag] = max(dp[i + 1][j][next_diag], dp[i][j][0] + next_hor + next_diag)
        dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][0] + next_hor)
        dp[i + 1][j ^ 1][0] = max(dp[i + 1][j ^ 1][0], dp[i][j][1] + next_diag)
print(max([dp[n - 1][0][1], dp[n - 1][0][0], dp[n - 1][1][1], dp[n - 1][1][0]]))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
s1 = list(input().rstrip())
s2 = list(input().rstrip())
(u, v) = ([], [])
for (i, j) in zip(s1, s2):
    u.append(i & 1)
    v.append(j & 1)
u.append(0)
v.append(0)
inf = pow(10, 9) + 1
dp0 = [inf] * 8
dp0[u[0] + 2 * v[0]] = 0
for i in range(1, n + 1):
    (u1, v1) = (u[i], v[i])
    dp = [inf] * 8
    for j in range(8):
        if dp0[j] == inf:
            continue
        dpj = dp0[j]
        (u0, v0, x) = (j & 1, j & 2, j & 4)
        if not x:
            if v0 and u1 and v1:
                dp[2] = min(dp[2], dpj + 1)
                dp[4] = min(dp[4], dpj + 1)
            elif v0 and u1:
                dp[0] = min(dp[0], dpj + 1)
                dp[4] = min(dp[4], dpj + 1)
            elif v0 and v1:
                dp[2] = min(dp[2], dpj + 1)
                dp[4] = min(dp[4], dpj)
            elif u1 and v1:
                dp[2] = min(dp[2], dpj)
            elif u1:
                dp[0] = min(dp[0], dpj)
            elif v1:
                dp[2] = min(dp[2], dpj)
            elif v0:
                dp[0] = min(dp[0], dpj + 1)
                dp[4] = min(dp[4], dpj)
            else:
                dp[0] = min(dp[0], dpj)
        elif u0 and u1 and v1:
            dp[0] = min(dp[0], dpj + 1)
            dp[5] = min(dp[5], dpj + 1)
        elif u0 and v1:
            dp[0] = min(dp[0], dpj + 1)
            dp[4] = min(dp[4], dpj + 1)
        elif u0 and u1:
            dp[0] = min(dp[0], dpj)
            dp[5] = min(dp[5], dpj + 1)
        elif u1 and v1:
            dp[5] = min(dp[5], dpj)
        elif v1:
            dp[4] = min(dp[4], dpj)
        elif u1:
            dp[5] = min(dp[5], dpj)
        elif u0:
            dp[0] = min(dp[0], dpj)
            dp[4] = min(dp[4], dpj + 1)
        else:
            dp[4] = min(dp[4], dpj)
    dp0 = dp
ans = sum(u) + sum(v) - min(dp0)
print(ans)