CHANDF - EDITORIAL

editorial
, , , , ,
38

Thanks anyways.

1 Like
39

Beauty of Bitwise ‘AND’

1 Like
40

Hey! the same happened to me. The solution got accepted when I changed unsigned long long to long long.

2 Likes
41

I think there is a solution in o(bits) as well for sub-task 2,correct me if i am wrong
using this solution sub-task 3 could be done in o(bits*bits),but with a smaller coefficient that using(x|y).
please do check.

42

I tried a few approaches with the common themes of only looking at numbers z such that z & (x|y) !=0 or z&x != 0 and z&y!=0, variations been z coming down from above in a specific range or going up etc.

They were all implemented in Python. But they all failed for subtask #2 with TLE (5.0+).

Now when I looked at the approach above I submitted one of my solutions with language set to PyPy. Solution failed again with TLE (2.0+). Lesson learnt - will switch to C++ for the up coming challenges. Learned some bit twiddling approaches as well. Thanks

43

Yes, there are can be multiple approaches. But this is a basic approach to this problem.
There are even beautiful recursive approaches to this problem.
You may have a look at them too.
xuanyiming’s solution
ei_captain’s solution

2 Likes
45

Hey I tried implementing the solution using your approach.
But i am getting Runtime-error , it is mostly because of overflow because if i remove

#pragma GCC optimize “trapv” // abort() on (signed) integer overflow.

this line from my code, it shows WA.

Submission
Can anyone hint why? :frowning:

46

Wow, they look so simple. orz :open_mouth:

47

You have to optimize your solution and find an approach for traversing bits and solving it.
You cannot loop from L to R.

1 Like
48

Hardifying problems: In the initial proposal there was some weird constraints with the intention of making the answer always equal to X&Y. After adding the bounds L,R for Z, even the setter had troubles solving the problem :slight_smile:

10 Likes
49

Great question @harshil21!! :fire:

This is a kind of question that seems easy when you read it for the first time and encourages more and more users to participate. Very creatively designed question. Looking forward to such questions!

10 Likes
50

Try this test case:

1
1133953 63182 0 595

Your answer -> 1179203
Expected answer -> 463

1 Like
51

Damn my answer is no where close.

52

Nice Editorial!!

1 Like
53

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?

54

the indexing started from 0 like in arrays

1 Like
55

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.

1 Like
56

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.

57

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

1 Like
58

same thing happened with me too.