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.

Author: 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:

\displaystyle \begin{align*}
B(30) &= B(15) + \mathtt{0} \\
&= B(7) + \mathtt{10} \\
&= B(3) + \mathtt{110} \\
&= B(1) + \mathtt{1110} \\
&= \mathtt{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) \mathbin{\&} (2^K - 1).

Time Complexity: \mathcal O(K)


  • -2
    ross_cleary  commented on Dec. 2, 2020, 4:44 p.m.

    For the bitwise operations solution, why isn't the time complexity the same as the recursive solution? Doesn't bitwise XOR have a time complexity of O(logN)?

    • 0
      Genius1506  commented on Dec. 2, 2020, 4:59 p.m.

      Bitwise XOR is O(1).