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

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$ $N$ by appending the remainder of $N$ $N$ divided by 2 to the binary representation of $N$ $N$ divided by 2.

If we let $B(N)$ $B (N)$ represent the binary representation of $N$ $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} \end{align*}$ $\begin{aligned} B (30) & = B (15) + 0 \\ = B (7) + 10 \\ = B (3) + 110 \\ = B (1) + 1110 \\ = 11110 \end{aligned}$

After obtaining the binary representations, we can loop through the last $K$ $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)$ $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)$ $(N \otimes M) & (2^{K} - 1)$ .

Time Complexity: $\mathcal O(K)$ $O (K)$

Comments

-1

ross_cleary commented on Dec. 2, 2020, 9:44 p.m. ← edited →

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 $\mathcal{O}(\log N)$ $O (\log N)$ ?

1

Genius1506 commented on Dec. 2, 2020, 9:59 p.m. ← edited →

Bitwise XOR is $\mathcal{O}(1)$ $O (1)$ .