CHANDF - EDITORIAL

editorial
, , , , ,
23

I started with B’s MSB and then checking if this bit is present in A, B or Ref (X|Y).
Then followed these rules:

  • present in A, then it should be part of Z in order to maintain Z >= A
  • not present in B, then it has to be discarded in order to maintain Z <= B
  • not present in A but in B, then
    a. take this bit and now Z is always greater than A and A is no longer a boundary. use bFunc to get desired value of Z
    b. discard this bit and now Z is always smaller than B and B is no longer a boundary. use aFunc to get desired value for Z

solution

1 Like
24

A great problem. I wasn’t able to solve it on my own.
Thanks for editorial!

2 Likes
25

thanks for reviewing my code ! so the overflow must be happening since i was converting bitset numbers to unsigned long ?

26

Yes, maybe the Number exceeds the declared size of bitset.

27

Nice editorial !!

1 Like
28

If it’s not much to ask could you also review my code or give me a test case where overflow may happen, as I have tried to generate test cases with X,Y\geq 10^9 but couldn’t generate the overflow. Great problem and editorial, thank you for doing it!

29

Not related but
Congrats @l_returns for 6 star :slight_smile:

1 Like
30

Your latest code fails on X, Y = 10^{11} and L = 0 and R = X - 1.
Here the max{F(X, Y, Z) } does not exceed the limits of the long long integer.
This probably is due to the difference between unsigned long long and long long where unsigned long long provides a wrong answer (which is astonishing).
Here both data types will provide different answers.(I’m not sure why tho)

3 Likes
31

Thank you for reviewing my code .
Can I ask for one more favor - Could you please tell how it is failing on given testcase?
I randomly tried inputs as per you mentioned but your code and my code gave same outputs.
Could you please provide testcase that is failing or suggest some potential changes in code?

32

Thank you so much!

33

Try some max limits of constraints, I’ve seen your code fail about max constraints.

1 Like
34

I am failing on it too. :frowning:
Why?

35

Hey I just removed unsigned before my long long everywhere and it passed.
How is unsigned happened to be failing? :frowning_face:

2 Likes
36

Thanks a lot :slight_smile:

1 Like
37

Actually, I have no idea but I will get back to that soon. :sweat_smile:
Maybe it’s some internal error but I’m not sure.

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