Obtaining the minimum number of tails of coin after flipping the entire row or column multiple times

Question

If coins are placed on a grid and only an entire row or column can be flipped, how can we flip the coins to obtain the minimum number of tails.

I tried to using the greedy solution, in which I flip the row or column where the number of tails are greater than heads and repeat the process until there exists no change on the number. But I found that this approach does not give me an optimal solution in some times.

HHT
THH
THT

For example, if the coins are placed like the above and I flip the coins in below manner, the obtained value is 3 but actually the answer is 2.

1. Flip the row 3
HHT
THH
HTH
2. Then there exists no row or column where the number of tails are greater than that of heads.
3. But if I flip the column 3, row 3, column 1, there exists a solution whose value is 2.
THH
HHT
HHH

So, I think the above algorithm doesn't work. What approach and what algorithm should I use?

Answer 1

First let us notice that there is no point in flipping the same row or column twice or more (a better solution is always either flipping the row/column zero or one time), and the order we flip the rows or columns is irrelevant, so we can describe a solution as a bit array of length 2N. One bit per row and one bit per column. On if we flip that row/column once, off if we flip it zero times.

So we need to search 2^(2N) possible solutions, prefering solutions with more zeros.

Secondly let us notice that for one solution there are four possible states of a coin:

1. The coin was not flipped (0 flips)
2. The coin was flipped by its row (1 flip)
3. The coin was flipped by its column (1 flip)
4. The coin was flipped by both its row and column (2 flips)

Notice that state 1 and 4 result in the original value of the coin

Also notice that state 2 and 3 result in the opposite of the original value of the coin

Start by expressing the original state of the coins as a binary matrix (B). The 2N-bit field as 2 binary vectors (R, C), and the total number of tails as a function of this f(B, R, C), and the total number of bits as a function g(V_1, V_2)

So your goal is to make f >= minimum while minimizing g.

Think that if we first fix our R configuration (which rows we will flip), how can we solve the problem just for C (which columns we will flip)? Put another way, consider the simpler problem of only being allowed to flip columns, and not being allowed to flip rows. How would you solve this? (hint: DP) Can you extend this stategy back to the full problem now?