CHANDF - EDITORIAL

editorial
, , , , ,
66

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

1 Like
67

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

68

yes i got that, forgot about that😅. Thanks

69

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!

70

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.

71

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.

72

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

73

Try this case!

1
8423128 9601744 4840 28872

Your answer -> 4840 , while expected answer -> 5848.

3 Likes
74

Isn’t 2^{70} greater than 10^{19} ? 2^{70} is even greater than 10^{21}

I have also checked with 10^{19} and it still gave RTE : CodeChef: Practical coding for everyone

With 10^{21} it also gave RTE in subtask2 :
https://www.codechef.com/viewsolution/33022337

It got AC with 10^{22} :
https://www.codechef.com/viewsolution/33022380

I don’t think it can be hold in long long integer

75

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.

1 Like
76

Yes, I see your point. Even, I am confused as I and tester verified by asserting in our respective solutions.
You can check it.

My sol

2 Likes
77

Perhaps the problem is that in your solution you are using the long long type and you can get overflow without even noticing it.

I changed a little bit your solution , using 128-bit integer data type and it also gave Run Time Error : CodeChef: Practical coding for everyone

1 Like
78

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.

79

Is it possible to solve this problem using Binary Search?(Just wanted to know) @harshil21

80

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. :wink:
PS. Here, brute force is running loop from l to r

2 Likes
81

Yes, I’ve shared to links to solutions of people who have used modified binary search to solve this question.

1 Like
82

I tried to solve the 2nd subtask, but don’t know what went wrong .
please provide me the test case where it is failing.

https://www.codechef.com/viewsolution/32911904

83

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.

6 Likes
84

i am trying to solve subtask2 .
But it is giving WA . Can somebody help me??
https://www.codechef.com/viewsolution/33027313

85

good problem and good editorial as well

1 Like