XORIT - Editorial

editorial
, , , ,
16

Sure. Consider the binary representation of the numbers. All the even numbers have their first bit equal to zero. Now if we omit the first zero in them, they’ll actually be divided by 2. So if we omit the first zero in all the even numbers in the interval [1,R], we’ll get all the numbers in the interval [1,\lfloor\frac{R}{2}\rfloor]. It’s easy to see that lb(2N) = lb(N)+1 since we’re adding a zero to the beginning of N. So 2^{lb(2N)} = 2^{lb(N)+1} = 2^{lb(N)} \times 2. So we can find the sum of the lowest bits of all the even numbers in the interval [1,R] via the some of the lowest bit of the numbers in the interval [1, \lfloor\frac{R}{2}\rfloor]. As explained above, this value is equal to G'(\lfloor\frac{R}{2}\rfloor) \times 2.

1 Like
17

Very Helpful!

1 Like
18

see basically I think you understood that when N=3 then B =2 and A =1 that is right most set bit and also A+B=N as they will not share any bit . for the condition A,B>=1&&A,B<=N then observe carefully all the odd values have first that is 0th rightmost bit as set in the numbers then in rest N/2 numbers the second rightmost bit will be set and it goes on till n reaches 0 This was a part to observe for example take l=1 r=10
there are 10 numbers
1 2 3 4 5 6 7 8 9 10
count of numbers having 0th bit as set =5(1,3,5,7,9) (ceil value of 10/2)
count of numbers having 1st bit as set=3(2,6,10) (ceil value of 5/2)
remaining numbers 5-3=2
count of numbers having 2nd bit as set=1(4) (ceil value of 2/2)
remaining numbers 2-1=1;
count of numbers having 3rd bit as set=1(8) (ceil value of 1/2)
remaining numbers 0
and process ends.
and it g

19

Nice explanation!

20

Hey! Would you please make a tutorial for 2nd question of december cook off PRFYIT
Link: CodeChef: Practical coding for everyone

1 Like
21

Great Explanation!

1 Like
22

Okay I’ll try to!

2 Likes
23

Thanks for the video. Keep up the good job.

1 Like
24

Can I do the below code.I know its complexity will be n^2 but the time it took was 1.01 secs(when converted to c++) ,have a look once and suggest some modification.

for i in range(int(input())):
x,y=input().split()
n=int(x)
m=int(y)
sum=0
def returner(i):
for j in range(1,i+1):
for k in range(j,i+1):
if myXOR(j,k)==i:
return k
break
return -1
def myXOR(x, y):
return ((x | y) & (~x | ~y))
for i in range(n,m+1):
sum=returner(i)+sum

print(sum)
25

Superb explanation!

1 Like
26

Thank you! I am asking because the editorial is not clear, by the way i like your videos. Way to go!

1 Like
27

hey can you explain the same for 10 17??
im getting 81 for that
as sum of B comes to be 8+10 +10 +12 +12 +14 -1 +16=81
plss help in clarify
thanks…

28

Sir, Thank you very much. Can you please make the video for second question. PRFYIT.

1 Like
30

Okay, for 12 ,

A = 4, B = 8, NOT 10

31

Thanku!! Nice explanation

1 Like
32

you can check out this tutorial for PRFYIT

33

oh yes got my mistake thank u so muchh

34

Please tell me how are we talking in terms of sum here? Calculating (N-A) when the operation in the question mentioned is clearly XOR? Thanks!!

35

Can you please tell how are we saying that A+B=N when the operation mentioned is A^B= N, please help!

36

As explained in the editorial, A and B shouldn’t have any common set bits in their binary representation. Knowing this fact, we can safely say that A + B = A \oplus B since \oplus is the same as addition, only without carry which we know we won’t need in adding A to B.

2 Likes