INVZCNT Editorial

editorial
,
15

No, It will not be affected.

1 Like
16

what is the time complexity of setter’s Solution??

1 Like
17

I mentioned complexity in the edit. check it

3 Likes
18

that’s really good question. I really wish i could think of it during contest. kudos to problem setter.

5 Likes
19

for(int bit = 0 ; bit < 31 ; bit++){
if( (K & (1<<bit)) ) ans += inv[bit][1];
else ans += inv[bit][0];
}
Please explain this part…
How it work , I understand the above code but can’t understand it…
Pls help

1 Like
20

Initially ans is set to zero and for each bit of k, depending on if that bit is set or not. inv[bit][set] or inv[bit][notset] is added to the answer.

1 Like
21

my doubt is that if the mth bit is set in k then it will unset the mth bit in arr[i] and set it, depending on the arr[i],so it will reverse the answer that is it kth bit is set then int[bit][0] is used because the all the kth unset bit will set after this operation…
I Think now u understand my doubt…
Thanks in advance.

22

I am sorry but I don’t understand what do you mean. It would be helpful if you can give an example or elaborate clearly.

1 Like
23

Sure and thanks for replying.
what i understood is that inv[bit][set] mean that if bit is set then it will provide inv[bit][set] of inversion to the answer…
now suppose that 12th bit is set in k then when I, xor k with each element then it will set or unset the 12th bit in array element then inv[12][0] will be added to the answer instead of inv[12][1]…

24

inv[b][0] represents the number of inversions contributed to the answer by the bit b. inv[b][1] represents the number of inversions contributed to the answer if the bit b is flipped in all the elements of arr[].

So if the bit b in k is 1, it means that the bit b in all the element of arr will be flipped. So inv[b][1] should be added to the answer for this bit. If the bit b in k is 0 then that bit in all the elements of arr will remain as original, hence inv[b][0] needs to be added to the answer.

An interesting thing to note: Contribution to the number of inversions due to each bit is independent of that by the other bits and hence they can be added to form the answer.

3 Likes
25

Awesome, Thanks u save my 2-3 hours.

1 Like
26

Such a beautiful question, great work by the setter.

27

can anyone explain me this solution in a simple way.I m not able to understand it

28

The solution is self explanatory, if you are stuck, you should be asking specific questions, the place where you are stuck.

1 Like
29

Can someone explain this?

Why can we add number of zeroes to left when we encounter a 1 to inv[bit][1] ?
I mean for an inversion 1 should be on the left and 0 on the right, or am I missing something ?
Please help !

30

Since we flipped the most significant bit, we should count number of zeroes to the left of some ones. So it’s correct. Actually it depends whether you do flip the values in the array then you will do the first way. If you don’t want to flip them, this is the way

2 Likes
31

Thanks a lot !

32

Can someone explain why I am getting TLE. My idea is exactly same as editorial but giving TLE. Code : https://www.codechef.com/viewsolution/27613831 @jafarbadour

33

you need to preprocess before query (only once)

34

it’s beautiful !