### ani_10's blog

By ani_10, history, 6 weeks ago,

May anyone please tell hoW numbers of black square is k(M − l) + (N − k)l.

B: fLIP

The order of pressing buttons doesn’t matter, and it doesn’t make sense to press the

same button

multiple times.

Suppose that we press exactly k row-buttons and l column-buttons. Then, the number of

black squares

will be k(M − l) + (N − k)l.

Thus, we can brute force all pairs (k, l), and check whether we can satisfy

k(M − l) + (N − k)l = K.

The complexity of this solution is O(NM).

Exercise: can you solve this problem in O(N)?

• -31

 » 5 weeks ago, # |   0 When you only flip $k$ rows, $kM$ squares turn black. When you only flip $l$ rows, $lN$ squares turn black. So why is the answer not $kM + lN$? There will be some squares which are flipped once when you press a row button, and flipped again when you press a column button. There are $kl$ squares have been counted twice, instead they should be not counted at all. So taking this into consideration, we get $kM + lN -2kl$ as our answer, which can be rearranged to become $k(M − l) + (N − k)l.$