CHANDF - EDITORIAL

editorial
, , , , ,
20

in problem it is said it won’t exceed 2^62

21

Your code shows an overflow error for X, Y \ge 10^{9}.

22

you should also check the case when either x=0 or y=0
the answer should be zero in that case.

1 Like
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