INVZCNT Editorial

editorial
,
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 !

35

what does z ,o and inv[100][2] signifies and why are we adding z in inv[bit][1] if bit is turned on
and o in inv[bit][0] when bit is turned off

1 Like
36

So, you have to count the number of inversions with respect to a given bit. For simplicity let’s start with the 0th bit. Now, let’s think of the condition when the inversion can take place - suppose we take a number from the input vector(say ar)at index i, and we are only taking into consideration the 0th bit here. So, for all such i such that ar[i] has 0th bit set(i.e.1) we take all such j, such that j < i and the 0th bit of number at this index, i.e. the 0th bit in ar[j] is unset(= 0). So, we have an inversion for this pair (i, j). So, for every i, we have to add all such js. Now, the thing is that the XOR operation that we have in each query, may flip these bits, so, 0 becomes 1 and vice versa. So, for this we have to find the reverse condition, i.e. all such (i, j) such that j < i but bit for j is set but unset for I.

1 Like
37

ok bro i got it…thanks for replying

1 Like
38

@jafarBadour but problem is after calculating xor we have to count xor?

and why do you calculate xor after flip bit?
and when you are saying you divide vector ,is’nt it not make binary tree of 0 or 1?

all these points are not understandable from your editorial !! please clarify it!!

BTW kudos for very nice problem and beutiful solution too

but still help to simplify its editorial ,bcoz it is hard to understand this beautiful question

39

I don’t understand your first 2 questions?

For the third question yes it’s almost like making binary tree. If you solved any xor problem before probably you should know it.

40

nice one sir
what if for base case
if(bit == -1 || v.size()<=1) return;
this should work.