### ani_10's blog

By ani_10, history, 7 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)? Comments (3)
 » 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.$
{"ft_lang_label":"__label__en","ft_lang_prob":0.7786038,"math_prob":0.995507,"size":1171,"snap":"2020-34-2020-40","text_gpt3_token_len":327,"char_repetition_ratio":0.11396744,"word_repetition_ratio":0.044334974,"special_character_ratio":0.29547396,"punctuation_ratio":0.115226336,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99942636,"pos_list":[0,1,2,3,4,5,6],"im_url_duplicate_count":[null,3,null,2,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-10-01T22:43:52Z\",\"WARC-Record-ID\":\"<urn:uuid:86739c3f-9eae-4960-b199-a7f8a7ebc949>\",\"Content-Length\":\"90286\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4d8615af-5fc7-47c4-818a-705127af6798>\",\"WARC-Concurrent-To\":\"<urn:uuid:250c6fa2-621e-49bb-b853-b60cfebdbb98>\",\"WARC-IP-Address\":\"81.27.240.126\",\"WARC-Target-URI\":\"https://codeforces.com/blog/entry/81484\",\"WARC-Payload-Digest\":\"sha1:D7C3DLXGWWLXJHTP2WHMVID7HK7U5CWE\",\"WARC-Block-Digest\":\"sha1:SSLYXIHIBPGQCIM4LVQUXF2ITNE7LDFF\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-40/CC-MAIN-2020-40_segments_1600402132335.99_warc_CC-MAIN-20201001210429-20201002000429-00772.warc.gz\"}"}