Editorial

As the OEIS shows,
$$$f(x)$$$ is the no. of $$$0's$$$ in binary representation of $$$x$$$.
We can also observe that $$$g(x)$$$ is decreasing after powers of $$$2$$$.
So, the best numbers for us are powers of $$$2$$$.
Now, there arise 2 cases:

• There is a power of $$$2$$$ between $$$L$$$ and $$$R$$$, in that case the highest of such numbers will be the most desired, and $$$f(x) + g(x)$$$ will be calculated for that.
• There is no power of $$$2$$$ between $$$L$$$ and $$$R$$$, then $$$g(x)$$$ will be maximum for $$$x = L$$$
  But, the maximum for $$$f(x)$$$ can't be determined easily.
  One noticeable point is that the range is $$${10^9}$$$, i.e. $$$31$$$ bits.
  So, we can check the max value of $$$f(i) + g(i)$$$ for $$$i$$$ from $$$L$$$ to $$$min(L + 31, R)$$$. (This is intuition based, and I couldn't find a concrete proof behind this.)

My Submission
(Note that it got accepted even for checking till $$$min(L + 13, R)$$$ [perhaps due to weak test cases].)

Ohh, I didn't know about Oeis but I just printed the pattern for i=1 to 20 using recursion by which I concluded that the local maximas occour at perfect powers of 2. So just find the greatest power of 2 in the range [l,r] and use recursion to get the answer as it will be logarithmic in time. What's left is the case where no perfect power of 2 lies in the range [l,r] here I printed all the values till 5000 and noticed that sometimes a small peak (deviation) is observed from the decreasing pattern from the perfect power of 2's value. For this, I used the fact that it lied just close enough to l and we could brute force all the values in the range [l,min(l+500,r)]. I have no actual proof that why choosing 500 worked (did'nt have that much time left for trying to prove my solution) but the decrease from f(l)+g(l) to f(min(r,l+500))+g(min(r,l+500)) was significant enough for it to get hold of any deviation and pass.

All editorials were made public soon after the contest ended: https://discuss.codechef.com/tag/start75