Let the board be represented as two rows of length $ n $, with each cell either empty (`'0'`) or occupied by a pawn (`'X'`).
A bishwock is an L-shaped tromino covering exactly three cells, and may be placed in any of four rotations:
- Type A: covers $(0, i), (0, i+1), (1, i)$
- Type B: covers $(0, i), (1, i), (1, i+1)$
- Type C: covers $(0, i+1), (1, i), (1, i+1)$
- Type D: covers $(0, i), (0, i+1), (1, i+1)$
for $ i \in \{0, 1, \dots, n-2\} $.
Each bishwock must be placed such that all three of its cells are **empty** (i.e., not occupied by pawns).
Bishwocks may not overlap and may not cover pawn-occupied squares.
Define:
- $ S_0, S_1 \in \{0, X\}^n $: the two rows of the board.
- $ \mathcal{P} \subseteq \{0,1\} \times \{0, \dots, n-1\} $: set of pawn-occupied positions.
We wish to find the maximum number of non-overlapping bishwocks that can be placed on empty cells.
This is a dynamic programming problem over columns.
Let $ dp[i][mask] $ be the maximum number of bishwocks that can be placed in columns $ 0 $ through $ i-1 $, where $ mask \in \{0,1,2,3\} $ encodes the occupancy status of the two cells in column $ i $:
- mask = 0: both cells (row0, row1) in column $ i $ are free (not covered by any bishwock extending from left)
- mask = 1: row0 occupied, row1 free
- mask = 2: row0 free, row1 occupied
- mask = 3: both occupied
But note: bishwocks span two columns. So we consider state transitions from column $ i $ to $ i+1 $, checking which bishwocks can be placed ending at or starting at column $ i $.
Alternatively, define state $ dp[i][a][b] $: maximum bishwocks placed up to column $ i $, with $ a, b \in \{0,1\} $ indicating whether cell $ (0,i) $ and $ (1,i) $ are **covered** by a bishwock that started at column $ i-1 $ (i.e., are already used and thus unavailable for new bishwocks starting at $ i $).
But since bishwocks span two columns, it’s better to process two columns at a time.
Standard approach for tiling problems:
Let $ dp[i] $ be the maximum number of bishwocks that can be placed in columns $ 0 $ to $ i-1 $, assuming that columns $ 0 $ to $ i-1 $ are completely filled (no overhangs).
But since bishwocks can leave partial coverage, we need state to represent the occupancy of the **current column** due to bishwocks extending from the left.
Actually, since each bishwock covers two consecutive columns, define:
Let $ dp[i][s] $ = maximum number of bishwocks placed in columns $ 0 $ to $ i $, where $ s \in \{0,1,2,3\} $ is a bitmask representing which cells in column $ i $ are already covered by a bishwock that started at column $ i-1 $.
But more cleanly:
We process column by column. At column $ i $, we consider placing bishwocks that start at column $ i $, which will cover column $ i $ and $ i+1 $. So we need to know the state of column $ i $ (which cells are free) and column $ i+1 $.
Actually, standard solution for this known problem (CodeForces "Bishwock") uses DP with state $ dp[i][mask] $, where $ mask $ is a 2-bit mask representing which cells in column $ i $ are already occupied (by a bishwock placed earlier). But since bishwocks extend to the right, we consider placing them starting at column $ i $, and the state is the occupancy of column $ i $ **before** placing any bishwock starting at $ i $.
**Formal DP Definition:**
Let $ dp[i][s] $ = maximum number of bishwocks that can be placed in columns $ 0 $ to $ i-1 $, with the state $ s \in \{0,1,2,3\} $ representing the occupancy status of column $ i $ **due to bishwocks placed in previous columns** (i.e., from column $ i-1 $).
- $ s = 0 $: both cells in column $ i $ are free
- $ s = 1 $: top cell occupied, bottom free
- $ s = 2 $: top free, bottom occupied
- $ s = 3 $: both occupied
But note: bishwocks placed starting at column $ i-1 $ may have covered column $ i $, so at column $ i $, we know which cells are already taken.
However, the board has pawns, so we must also check that no bishwock is placed on a pawn.
Let $ board[0][i] $, $ board[1][i] \in \{0, X\} $ be the input.
Define $ \text{free}[r][i] = 1 $ if $ board[r][i] = '0' $, else 0.
At column $ i $, the available free cells are those that are both:
- not occupied by a pawn, and
- not already covered by a bishwock from the left (as encoded in state $ s $).
So the **available** cells at column $ i $ are:
- $ a_0 = \text{free}[0][i] \land (s \& 1 == 0) $ // top cell available
- $ a_1 = \text{free}[1][i] \land (s \& 2 == 0) $ // bottom cell available
We now consider placing zero or more bishwocks starting at column $ i $. Since each bishwock spans two columns, we look at column $ i $ and $ i+1 $.
We try all possible bishwock placements starting at column $ i $ that cover three of the six cells: (0,i), (1,i), (0,i+1), (1,i+1), under the constraint that:
- The three cells covered are all available (free and not already covered),
- And the placement is one of the four valid L-shapes.
Then we update the state for column $ i+1 $.
The four possible bishwocks starting at column $ i $:
1. **Type A**: covers (0,i), (0,i+1), (1,i)
→ requires: a0, free[0][i+1], a1
→ leaves column $ i+1 $ with bottom cell covered → state = 2
2. **Type B**: covers (0,i), (1,i), (1,i+1)
→ requires: a0, a1, free[1][i+1]
→ leaves column $ i+1 $ with top cell covered → state = 1
3. **Type C**: covers (0,i+1), (1,i), (1,i+1)
→ requires: free[0][i+1], a1, free[1][i+1]
→ leaves column $ i+1 $ with top cell covered → state = 1
4. **Type D**: covers (0,i), (0,i+1), (1,i+1)
→ requires: a0, free[0][i+1], free[1][i+1]
→ leaves column $ i+1 $ with bottom cell covered → state = 2
Also, we can place **no** bishwock at column $ i $, then state for column $ i+1 $ is 0, provided that column $ i $ is fully cleared (but we don’t need to clear it — we just move on).
Actually, since we are at column $ i $, and state $ s $ tells us what’s already covered from the left, we must ensure that after placing bishwocks starting at $ i $, the entire column $ i $ is covered (either by prior bishwocks or new ones). But we are allowed to leave column $ i $ with some cells uncovered if they are blocked by pawns? No — we can leave free cells uncovered, but we cannot place a bishwock on a pawn.
Important: We are not required to cover all free cells. We want to maximize the number of bishwocks.
So we can leave free cells empty. Therefore, we do **not** require that column $ i $ becomes fully covered. We just place as many bishwocks as possible, and the state $ s $ only encodes **which cells in column $ i $ are already occupied by bishwocks from column $ i-1 $**.
Thus, at column $ i $, we have:
- The state $ s $: cells in column $ i $ already covered by previous bishwocks.
- The pawn positions: which cells are blocked.
We can place a bishwock starting at column $ i $ only if the three cells it covers are:
- Not blocked by pawns, and
- Not already covered by a previous bishwock (i.e., not in state $ s $ for column $ i $, and not blocked in column $ i+1 $).
We consider placing **one** bishwock (or none) at column $ i $, and then move to column $ i+1 $.
We also consider the possibility of placing **two** bishwocks overlapping? No, each cell can be covered only once.
Actually, at one column, we can place at most one bishwock, since each bishwock uses two columns and three cells, and we only have two cells per column.
So at each column $ i $, we consider:
- Option 1: Place no bishwock starting at $ i $. Then the state for column $ i+1 $ is 0 (no coverage from left), **but** we must account for the fact that the current column $ i $ may have some free cells left — that’s fine.
Wait, no: the state for the next column should reflect whether any cell in column $ i $ is covered by a bishwock that started at $ i-1 $ — which is already encoded in $ s $. When we move to column $ i+1 $, the only coverage from the left is from bishwocks placed at column $ i $.
So if we place a bishwock starting at $ i $, it will cover one or two cells in column $ i+1 $, and we update the state accordingly.
If we place no bishwock at $ i $, then column $ i+1 $ has no bishwock extending from the left → state = 0.
But we must ensure that we are not "leaving" a cell in column $ i $ uncovered that could have been used — but since we are maximizing, and bishwocks are L-shaped, we can always delay placement.
Thus, recurrence:
For each column $ i \in [0, n-1] $, and state $ s \in \{0,1,2,3\} $:
- Let $ a_0 = \text{free}[0][i] \land \neg (s \& 1) $ // top cell available at column $ i $
- Let $ a_1 = \text{free}[1][i] \land \neg (s \& 2) $ // bottom cell available at column $ i $
If $ i == n-1 $: we cannot place any bishwock starting here (needs column $ i+1 $), so only option is to move to end.
Otherwise:
Option 1: Place no bishwock at $ i $.
Then $ dp[i+1][0] = \max(dp[i+1][0], dp[i][s]) $
Option 2: Try each of the four bishwock types, if possible.
For each type, check:
- The three required cells are available (i.e., not blocked by pawn and not already covered)
- The two cells in column $ i+1 $ are not blocked by pawns
Then compute the new state for column $ i+1 $, and update.
The four types:
1. Type A: covers (0,i), (1,i), (0,i+1)
→ needs: a0, a1, and free[0][i+1]
→ covers column $ i+1 $ at top → new state = 1
→ update: $ dp[i+1][1] = \max(dp[i+1][1], dp[i][s] + 1) $
2. Type B: covers (0,i), (1,i), (1,i+1)
→ needs: a0, a1, free[1][i+1]
→ covers column $ i+1 $ at bottom → new state = 2
→ update: $ dp[i+1][2] = \max(dp[i+1][2], dp[i][s] + 1) $
3. Type C: covers (1,i), (0,i+1), (1,i+1)
→ needs: a1, free[0][i+1], free[1][i+1]
→ covers column $ i+1 $ at top → new state = 1
→ update: $ dp[i+1][1] = \max(dp[i+1][1], dp[i][s] + 1) $
4. Type D: covers (0,i), (0,i+1), (1,i+1)
→ needs: a0, free[0][i+1], free[1][i+1]
→ covers column $ i+1 $ at bottom → new state = 2
→ update: $ dp[i+1][2] = \max(dp[i+1][2], dp[i][s] + 1) $
Initial state: $ dp[0][0] = 0 $, and for $ s \neq 0 $, $ dp[0][s] = -\infty $ (impossible)
Final answer: $ \max(dp[n][0], dp[n][1], dp[n][2], dp[n][3]) $
But note: at column $ n $, we have processed all columns. Since bishwocks cannot extend beyond column $ n-1 $, any state at column $ n $ is acceptable — we just take the max.
This DP runs in $ O(n \times 4) = O(n) $, which is efficient for $ n \leq 100 $.
**Final Mathematical Formulation:**
Let $ n $ be the length of the input strings.
Let $ b_0, b_1 \in \{0,1\}^n $, where $ b_r[i] = 1 $ if the cell at row $ r $, column $ i $ is empty (`'0'`), else $ 0 $.
Define $ dp[i][s] $ for $ i \in \{0, 1, \dots, n\} $, $ s \in \{0,1,2,3\} $, as the maximum number of bishwocks that can be placed in columns $ 0 $ to $ i-1 $, with $ s $ encoding the coverage of column $ i $ by bishwocks from column $ i-1 $:
- $ s = 0 $: no cell in column $ i $ is covered by a bishwock from column $ i-1 $
- $ s = 1 $: only cell $ (0,i) $ is covered
- $ s = 2 $: only cell $ (1,i) $ is covered
- $ s = 3 $: both cells are covered
Initial condition:
$ dp[0][0] = 0 $, and $ dp[0][s] = -\infty $ for $ s \in \{1,2,3\} $
For each $ i \in \{0, 1, \dots, n-1\} $ and each $ s \in \{0,1,2,3\} $, if $ dp[i][s] > -\infty $:
Let
- $ a_0 = b_0[i] \land \neg (s \& 1) $
- $ a_1 = b_1[i] \land \neg (s \& 2) $
**Option 1**: Do not place any bishwock starting at column $ i $:
→ $ dp[i+1][0] \gets \max(dp[i+1][0], dp[i][s]) $
**Option 2**: Place bishwock of type A if $ a_0 \land a_1 \land b_0[i+1] $:
→ $ dp[i+1][1] \gets \max(dp[i+1][1], dp[i][s] + 1) $
**Option 3**: Place bishwock of type B if $ a_0 \land a_1 \land b_1[i+1] $:
→ $ dp[i+1][2] \gets \max(dp[i+1][2], dp[i][s] + 1) $
**Option 4**: Place bishwock of type C if $ a_1 \land b_0[i+1] \land b_1[i+1] $:
→ $ dp[i+1][1] \gets \max(dp[i+1][1], dp[i][s] + 1) $
**Option 5**: Place bishwock of type D if $ a_0 \land b_0[i+1] \land b_1[i+1] $:
→ $ dp[i+1][2] \gets \max(dp[i+1][2], dp[i][s] + 1) $
Final answer:
$ \max_{s \in \{0,1,2,3\}} dp[n][s] $
This is the formal mathematical representation.