XORIT - Editorial

editorial
, , , ,
4

Was wandering with the same approach last night but you clarified my doubt very clearly .Hats off to you @kmaaszraa for nice question and then nice editorial.

5

can anybody explain why need to mutiply by 2 in case of even numbers .

6

Have a looka t these for easy solution
comment if you do not understand anything
my solution

7

So the value of their lowest bit is also multiplied by two in case of even numbers. I am unable to understand why we need to multiply by two ??

1 Like
8

Absolutely amazing the way the total number of numbers having a particular bit set was founded, i had to struggle a lot to find those numbers, nice question and editorial

9

Basically, you have to add,

(2 ^ i) * (count of numbers from (1 to N), whose LSB is in the ith bit.

and for every bit, you also have to add 1 to the previous result. ( because, for cases like :

1, 2, 4, 8, 16 …

The total generated value is the SUM of A only.

Let X = SUM of A only.

Now, subtract the X from SUM of [1.... N] .

Examples :
1
1 10

Lets us break it into the 4 bit representation :

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0

Now,
LSB ( 0th bit ) = 5 * (2 ^ 0) = 5
LSB ( 1st bit ) = 3 * (2 ^ 1) = 6
LSB ( 2nd bit ) = 1 * (2 ^ 2) = 4
LSB ( 3rd bit ) = 1 * (2 ^ 3) = 8

Add them along with a ( + 1 ) in each step to deduct the powers of two.

Now, SUM OF A = 23 + 4 = 27.

SUM OF B = 55 - 27 = 28. :slight_smile:

12 Likes
10

I’m plain dumb, yesterday tried the question for over an hour and now unable to understand the “EXPLANATION” part of EDITORIAL.

1 Like
11

Am getting a TLE in my solution. I added the optimisation for odd values. Not sure how else i can optimise this further. Can someone help out?
https://www.codechef.com/viewsolution/28459823

12
19 Likes
13

i didn’t under stand the even part approach can you elaborate

14

I’m Glad that you liked the problem!

15

Glad you liked the problem! :slight_smile:

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