CHANDF - EDITORIAL

[better_sleep]

Damn my answer is no where close.

[mayankg20]

Nice Editorial!!

[sumit_9398]

Let’s represent the numbers as binary strings, and denote the iii-th most significant bit of number S by S[i]. For example the string (binary) representation of 18 is S=10010, note that S[3]=1.

This is quoted from the NOTATION part para 2. Can you please explain why S[3] = 1?

[krishna_kc]

the indexing started from 0 like in arrays

[reena_code_123]

I tried to solve the subtask, but don’t know what went wrong .
x|y
https://www.codechef.com/viewsolution/32692655
https://www.codechef.com/viewsolution/32692466

Am I doing anything other than x|y.

[mohit3999]

For the first sub task, i thought the same but it produced wrong result.
Here is my solution:
https://www.codechef.com/viewsolution/32933172
Please help.

[reena_code_123]

Basically Our goal in this problem is to preserve maximum the set bits for both of and terms while keeping the value in the range L to R…We can hard code the logic to which bit can be set such that it maximizes the product and is the smallest wouldn’t that work?

See my Implementation:: CodeChef: Practical coding for everyone

[mohit3999]

same thing happened with me too.

[harshil21]

“Common error”
Try X = 0 and Y = 3 and L = 0, R = 10?
Answer should be 0.

[krishna_kc]

@reena_code_123 There is a corner case when x or y is zero. Because then no matter whichever z you choose value of the function stays zero. so minimum value of z in that case would be 0. This is under common errors. Did the same mistake

Beware of cases where X,Y,L,R = 0X,Y,L,R=0.

[reena_code_123]

Time to die…“Ohh bhai maro …mujhe maroo ”
I attempted several times …also in python but didn’t thaught of
R=0;

[reena_code_123]

Checking for R=0??

[mohit3999]

@harshil21 @krishna_kc Don’t see the solution, i got it , Mistakely, I added return their.

[harshil21]

Try removing return from your solution in the “if” statements.

[mohit3999]

@reena_code_123 yes checked for it, Now working fine​:sweat_smile:. One more silly mistake i made was adding the return statement.

[mohit3999]

yes i got that, forgot about that😅. Thanks

[deep2905]

Can someone tell me what’s wrong in my solution ?
I exploit fact that function have period of (2^k - 1) where k is max MSB. I get AC in first two sub tasks. Dont worry about TLE in 1 test case i can fix that but why i get WA in others ?
Because i’ve checked it with custom cases it gives right answer…
https://www.codechef.com/viewsolution/32907916

Thanks in advance!

[diegohdmgz]

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.

• In this code you can see that in all testcases , max_{L \leq K \leq R}(F(X, Y, K)) exceeds 2^{65} : CodeChef: Practical coding for everyone

• In this code you can see that in subtask 2 , max_{L \leq K \leq R}(F(X, Y, K)) exceeds 2^{70} : CodeChef: Practical coding for everyone

• Now the same code gets AC if I put a limit of 2^{75} : CodeChef: Practical coding for everyone

[harshil21]

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.

[haha_haha_haha]

@harshil21

Let k be the longest common preffix of L and R, then Z[0…k−1] = L[0…k−1] = R[0…k−1] , since the first index at which L and R are different is k, then R[k]=1 and L[k]=0(because L < R).

however in case of 10 (01010) , and 16 (10000) R[k] = 0 but L[k] = 1 for k =1 Can somebody justify that ?