ani_10's blog

By ani_10, history, 7 weeks ago, In English

https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_b

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)?

 
 
 
 
  • Vote: I like it
  • -31
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

anyone please help me out

»
6 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

newbies life matters

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.$$$