Algorithms question: flipping columns

Question

Suppose that we are given an m x n grid of zeros and ones and want to transform the grid so that the maximum number of rows are composed solely of ones. The only operation we are allowed to perform on the grid is picking some column and flipping all of the zeros and ones in that column. We are also given some integer k and must perform exactly k columns flips. Given the grid and the value of k, how do we determine which columns to flip to maximize the number of rows that are all ones?

I'm thinking something dynamic would need to be done, but I'm not able to arrive at a good answer. Can someone help out?

Answer 1

Let's begin by thinking about an important detail of the problem: if two rows contain a column that differ across the rows (for example, in one row it's a zero and in one row it's a one), then there is no possible way to make both rows all ones. To see this, suppose that row x has a zero in some column and row y has a one in that column. Then if we don't flip that column, row x can't be all ones, and if we do flip the column then row y can't be all ones. Consequently, if we take a look at the original matrix and try to think about what rows we are going to make all ones, we are essentially just going to pick some set of rows that are all equal to one another. Our goal is then to pick the set of identical rows that is as large as possible and can be made into all ones using exactly k flips. Let's say that a row that can be made into all ones using exactly k flips is a "candidate row.". Then we just need to find the candidate row in the matrix that appears the greatest number of times.

The actual algorithm for doing this depends on whether or not we are allowed to flip the same column twice. If we aren't, then a candidate row is one that has exactly k zeros in it. If we can flip the same column multiple times, then this is a bit trickier. To make the row all ones, we would need to convert each zero to a one, then would need to keep spending the remaining flips flipping the same column twice to avoid changing any one to a zero. This is true if the difference between k and the number of zeros in the row is a nonnegative even number.

Using this, we get the following algorithm:

1. Maintain a hash table mapping from candidate rows to their frequency.
2. For each row:
   1. Count the number or zeros in the row.
   2. If the difference between k and this number is a nonnegative even number, update the hash table by incrementing the frequency of this particular row.
3. Find the candidate row in the hash table with the greatest total frequency.
4. Output the frequency of that row.

Overall, on an m x n matrix (m rows, n columns), we visit each row once. During the visit, we do O(n) work to count the number of zeros, then O(1) work to see if it is valid. If so, it takes an expected O(n) time to update the hash table, since the hashing step takes O(n) time to hash the row. This means that we spend O(mn) time filling in the table. Finally, the last step takes time O(m) to find the max frequency row, for a net runtime of O(mn), which is linear in the size of the input. Moreover, this is asymptotically optimal, since if we spent less time than this we couldn't look at al, the matrix elements!

Hope this helps! This is a cool problem!