4
$\begingroup$

We've got an $N \times M$ matrix whose elements are either zero or one. For example:

$\begin{bmatrix} 1 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 & 1\\ 1 & 1 & 0 & 0 & 1\\ 1 & 1 & 0 & 0 & 1\\ \end{bmatrix}$

You are allowed to toggle the values of any given column in the matrix. If you toggle a column, 0s become 1 and 1s become 0 in it. e.g. toggling the second column will result in:

$\begin{bmatrix} 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 1\\ \end{bmatrix}$

As you can see, the first row became all ones. What's the maximum number of rows that can become all ones after applying $K$ number of toggles? You can toggle a column multiple times and you are not allowed to perform the toggle less than $K$ times. Constraints: $1 \leq N \leq 50 $ and $1 \leq M \leq 20 $

$\endgroup$
  • $\begingroup$ Are we starting with a general $N\times M$ matrix, so that the final answer could depend on $N$, $M$, and $K$? (I.e. we're not starting from the $5\times5$ matrix you drew - that's just an example?) $\endgroup$ – Rand al'Thor Aug 23 '17 at 13:14
  • $\begingroup$ @Randal'Thor Yes that's just an example. $\endgroup$ – Meysam Aug 23 '17 at 13:15
6
$\begingroup$

The answer is

however many times the most common row with at most $K$ 0s and the same parity as $K$ 0s in it appears.

Proof:

First, note that toggling a column does not change whether two rows are identical. Thus, if two rows end up with all 1s, they must have been identical to begin with. Then the most common row which can be made into all 1s is the maximal choice. Any row with at most $K$ 0s can be toggled into the all 1s row with at most $K$ steps. Thus, the most common row with at most $K$ 0s is the best choice, and however many times that row appears is the most all-1 rows we can end up with. The number of 0s in the most common row must also have the same parity as $K$, as we alter the parity with each toggle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.