Contest Duration: - (local time) (100 minutes) Back to Home

## E - Don't Isolate Elements Editorial by spheniscine

To make implementation and explanation a bit easier, let’s add a “border” to $$A$$, that is, rows $$0$$ and $$H+1$$, similarly columns $$0$$ and $$W+1$$. They should be filled with a sentinel value that isn’t $$0$$ or $$1$$, including when “flipped” (e.g. $$2$$), and we also will stipulate that they will never count as isolated.

Now let’s define $$dp[i, a, b]$$ as the minimum cost such that rows $$0$$ to $$i$$ inclusive are valid, and $$a$$ and $$b$$ are each $$0$$ or $$1$$, depending on whether rows $$i$$ and $$i+1$$ should be flipped, respectively. (If there are no valid states, $$dp[i, a, b] = \infty$$.) We initialize the DP with $$dp[0, 0, 0] = 0$$ and $$dp[0, 0, 1] = 1$$, with the rest being $$\infty$$. (as it makes no sense to “flip” the sentinel row)

We can transition from $$dp[i, a, b]$$ to $$dp[i+1, b, c]$$ because for each $$c \in \{0, 1\}$$, we can check the $$i+1$$-st row for validity, since we know whether rows $$i$$ through $$i+2$$ should be flipped. This means we have $$2^3 = 8$$ total cases/masks to check for each row, so the total time to run this DP is $$O(HW)$$.

The final answer is $$\min(dp[H, 0, 0], dp[H, 1, 0])$$. If this is $$\infty$$, we should print $$-1$$.

posted:
last update: