Editorial for DMOPC '18 Contest 5 P1 - A Painting Problem


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: Kirito

We can recursively generate the binary representation of a number N by appending the remainder of N divided by 2 to the binary representation of N divided by 2.

If we let B(N) represent the binary representation of N, then we have:

B(30) = B(15) + `0' = B(7) + `10' = B(3) + `110' = B(1) `1110' = `11110'

After obtaining the binary representations, we can loop through the last K characters, and count the number of positions with the same character, and print the answer.

Time Complexity: \mathcal O(\log(N) + \log(M) + K)

Alternatively, if one is familiar with bitwise operations, this problem is the same as counting the number of bits set in (N \otimes M) \& (2^K - 1).

Time Complexity: \mathcal O(K)


Comments

There are no comments at the moment.