Problem G
Matrix Fraud
For the purposes of this problem: A matrix is a binary matrix if all its entries are $0$ or $1$. A matrix is a banded binary matrix if its rows and columns satisfy the following properties:
-
Every row has at least one $1$.
-
Every column has at least one $1$.
-
All $1$s in each row are contiguous.
-
For row $i$, if $s_ i$ is the leftmost column that has a $1$ entry and $t_ i$ is the rightmost column that has a $1$ entry, then it must satisfy $s_ i \ge s_{i-1}$ and $t_ i \ge t_{i-1}$ for $i > 1$.
Detecting banded binary matrices is an important method used in various fields like biology, paleontology, and linguistics to unearth clusters in data sets. Unfortunately, a group called the Immoral Cartel of Pure Cozeners (ICPC) has decided to do the unthinkable: manipulate data! The ICPC wishes to present their groundbreaking scientific results, but the scientific community will not take their results seriously because their matrices may not be banded. To have publishable results, they want to toggle some cells such that their data is a banded binary matrix.
The ICPC gives you its raw data, represented as a binary matrix. They want to toggle some cells (meaning, change a $0$ to a $1$ or a $1$ to a $0$) so that the resulting matrix is a banded binary matrix, as defined above. What is the fewest number of toggles needed to turn the given matrix into a banded binary matrix?
Input
The first line of input contains two integers $r$ and $c$ ($1 \leq r \times c \leq 2 \cdot 10^5$), which are the dimensions of the matrix. The matrix has $r$ rows and $c$ columns.
Each of the next $r$ lines contains a string of binary digits of length $c$. This is the matrix.
Output
Output a single integer, which is the minimum number of entries in the matrix to toggle to make the input matrix a binary banded matrix.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 1100 0101 0011 |
1 |
