Coin Flips
Time limit2sMemory limit128 MB
Find the minimum number of row and column flips on an odd N by M 0/1 grid so every row and column has an even count of 1s, or output -1.
- Level
Medium6 of 10
- Topics
- Math, Bit manipulation, Matrix, Brute force
- Solved
- No attempts yet
Problem
Coins are placed on an N×M grid. Both N and M are odd. A coin showing heads is written as 0, and a coin showing tails is written as 1.
In one operation, choose exactly one row or one column and flip every coin in it. A flipped coin changes from 0 to 1 or from 1 to 0.
Your goal is to make the number of 1s even in every row and every column. Find the minimum number of operations needed.
Input
The first line contains the height N and width M of the grid. N and M are odd integers not greater than 1,000.
Each of the next N lines contains a string of length M. Every character is either 0 or 1 and describes the current state of the coins.
Output
Print the minimum number of operations needed to make the number of 1s even in every row and every column. If it is impossible, print -1.
Hint
In the first public test, flipping the middle row and the middle column satisfies the condition.