I’m not sure if there is something wrong with my code or with the constraint that max_{L \leq K \leq R}(F(X, Y, K)) \leq 2^{62}. Maybe someone can help me to understand what is happening.
I have answered this question in many comments during live contest.
Actually, you’re partly correct as max_{L \le K \le R}(F(X,Y,K)) is not less than 2^{62} but it surely befits the limits of long long integer which is 10^{19}.
I have verified it from the test data.
Try asserting your solution with the above limit.
Also, as it didn’t make much difference because long long integer could hold the value of max_{L \le K \le R}(F(X,Y,K)).
Sorry for the inconvenience.
Here, we have no common prefixed set bits.
So here, k = 0. Therfore, R[0] = 1 but L[0] = 0.
‘k’ is the longest common prefix of L and R, it is fixed for any given instance.
Noted.
But as the note said that answer could fit the limits of long long integer, we’ll keep it as it is.
Thanks for the information and sorry for the inconvenience.
It is always best to use a random test case generator.
Let me tell you what I did to debug my code-> I wrote a brute force solution and created a random test case generator which ran over 1000 cases and compared ans of my brute force with actual solution and gave me the test cases where ans was different.
PS. Here, brute force is running loop from l to r
MIND-BLOWING … I was testing my solution during contest via comparison with brute force approaches to verify. While searching for alternative ways I printed the (X&MASK)*(Y&MASK) for all L<=MASK<=R, found an interesting pattern of several contigous subarrays with increasing numbers. I started towards working my way through finding each increasing subarray’s starting point in range L and R based on X and Y and failed miserably. Just thought wouldn’t it be nice to solve this via binary search and after a lot of effort I gave up thinking it was a crap idea and then here it is, that idea being made possible. It is an excellent problem, please keep on contributing such problems @harshil21 If possible please update the editorial with binary search approach too.
Yeah, this strategy helped me a lot too because with pen and paper it’s too hard to come up with the exact answer. Many times I got the function maximized but the value of z was no minimum.
