Solution


Approach 1: Brute Force

Intuition

Notice that a 1 in the th column from the right, contributes to the score.

Say we are finished toggling the rows in some configuration. Then for each column, (to maximize the score), we'll toggle the column if it would increase the number of 1s.

We can brute force over every possible way to toggle rows.

Algorithm

Say the matrix has R rows and C columns.

For each state, the transition trans = state ^ (state-1) represents the rows that must be toggled to get into the state of toggled rows represented by (the bits of) state.

We'll toggle them, and also maintain the correct column sums of the matrix on the side.

Afterwards, we'll calculate the score. If for example the last column has a column sum of 3, then the score is max(3, R-3), where R-3 represents the score we get from toggling the last column.

In general, the score is increased by max(col_sum, R - col_sum) * (1 << (C-1-c)), where the factor (1 << (C-1-c)) is the power of 2 that each 1 contributes.

Note that this approach may not run in the time allotted.

Complexity Analysis

  • Time Complexity: , where is the number of rows and columns in the matrix.

  • Space Complexity: in additional space complexity.


Approach 2: Greedy

Intuition

Notice that a 1 in the th column from the right, contributes to the score.

Since , maximizing the left-most digit is more important than any other digit. Thus, the rows should be toggled such that the left-most column is either all 0 or all 1 (so that after toggling the left-most column [if necessary], the left column is all 1.)

Algorithm

If we toggle rows by the first column (A[r][c] ^= A[r][0]), then the first column will be all 0.

Afterwards, the base score is max(col, R - col) where col is the column sum; and (1 << (C-1-c)) is the power of 2 that each 1 in that column contributes to the score.

Complexity Analysis

  • Time Complexity: , is the number of rows and columns in the matrix.

  • Space Complexity: in additional space complexity.


Analysis written by: @awice.