INVZCNT Editorial

PROBLEM LINK:

Practice
Contest

Author & Editoralist: Jafar Badour
Tester: Teja Reddy

PROBLEM EXPLANATION

You are given a sequence of non-negative integers A_1, A_2, \ldots, A_N. A pair (x, y), where 1 \le x \lt y \le N, is an inversion if A_x \gt A_y.

You should answer Q queries (numbered 1 through Q). For each valid i, in the i-th query:

  • You are given a non-negative integer K_i.
  • Consider a sequence B_1, B_2, \ldots, B_N, where B_j = A_j \oplus K for each valid j.
  • You should find the number of inversions in the sequence B.

PREREQUISITES:

None

QUICK EXPLANATION:

Start with bits from most significant to least significant. Find inversions with respect to each bit. After you finish processing the current bit, split elements into 2 vectors (one for numbers having this bit and one for rest). and calculate inversions w.r.t next bit for each vector separately. Answering queries is easy after that.

EXPLANATION:

Let’s assume that we want to solve inversions count on an array of values 0 and 1 only. This can be done easily in linear time. Whenever we encounter a 0 we should add the number of 1s to the left to our inversions count.

Let’s think about the most significant bit b.

Any pair x,y such that (x<y)\,\,AND\,\,(A_x\,\&\,2^b>0)\,\,AND\,\,(A_y\,\,\&\,2^b=0) forms an inversion, regardless of the rest of the binary representation.

Let’s find the number of inversions w.r.t the most significant bit (which is equal to 30 in our problem) and record the number of inversions and denote it with I_{msb}.

What do you think will happen if we flip this bit?

We can find the number of inversions the same way as we did first, whenever we encounter a 1 we should add the number of 0s to the left to our inversions count.

What about the rest of the bits? After finding inversions w.r.t most significant bit, we must find inversions between numbers that have an equal value of this bit.(For different we already did). Split elements into 2 vectors (one for numbers having this bit and one for rest). and calculate inversions w.r.t the next bit (msb-1) for each vector separately.

Let’s denote with I_b the number of pairs (x,y) such that x<y and the first different bit in the binary representation of A_x,A_y is the b_{th} bit, and A_x has this bit turned on.

Let’s say we have a vector v of length l and we are currently processing the bit numbered b and we have found x inversions w.r.t this bit. We flip this bit and calculate the invesions count again (as we did for MSB) and find inversions count after flipping and let’s denote this count by y.

I_b=I_b+x
I'_b=I'_b+y

Try to guess what’s I'b

How to find an answer for each query?

ans=0
Iterate through all bits from 0 to 30 and let’s say the current has index b
If the bit is turned off:
ans=ans+I_b
Otherwise:
ans=ans+I'_b

#Complexity O(N*log(Max \,A_i))

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MX = (1<<20);
int arr[MX];
long long inv[100][2];

void solve(int bit , vector < int > v){
	if(bit == -1 || v.empty()) return;
	int sz = v.size();
	int z = 0 , o = 0;
	vector < int > v1 , v2;
	for(int j = 0 ; j < sz ; j++){
		if( (v[j] & (1<<bit)) ){
			v1.push_back(v[j]);
			++o;
			inv[bit][1] += z;
		}
		else{
			v2.push_back(v[j]);
			++z;
			inv[bit][0] += o;
		}
	}
	solve(bit - 1 , v1);
	solve(bit - 1 , v2);
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		memset(inv , 0 , sizeof(inv));
		int n , QN;
		scanf("%d %d",&n,&QN);
		vector < int > v;
		for(int j = 0 ; j < n ; j++){
			int x;
			scanf("%d",&x);
			v.push_back(x);
		}
		solve(30 , v);
		for(int j = 0 ; j < QN ; j++){
			long long ans = 0;
			int K;
			scanf("%d",&K);
			for(int bit = 0 ; bit < 31 ; bit++){
				if( (K & (1<<bit)) ) ans += inv[bit][1];
				else ans += inv[bit][0];
			}
			printf("%lld\n",ans);
		}

	}
}
20 Likes

Nice problem. Can somebody suggest similar problems for practice?

3 Likes

Could you please explain this?? What is n and l here?

1 Like

N is the size of the input array. With an array of size N, there can be \frac{N.(N-1)}{2} total pairs. So, if I_{B} is the inversion with respect to 0th bit, then subtracting this number from total possible pairs would give you the inversion if this bit were flipped.

3 Likes

I have solved this problem by actually calculating the inversions after flipping the bits. I feel that subtracting the number of inversions from the total number of pairs (n*(n-1)/2) will not give the number of inversions if this bit is flipped.

Consider four numbers: 1 0 1 0
The total number of inversions is 3.

If we flip the bits to get: 0 1 0 1
The total number of inversions is 1. which is not equal to 4*3/2 - 3.

@jafarbadour Please correct me if I am wrong.

3 Likes

I am sorry for such stupid mistake. I will correct the mistake and update again.
My apologies. I was in a very bad mood after the issue that happened in the contest and I wrote a wrong formula, sorry :frowning:
Edit: Updated

3 Likes

@jafarbadour can u pls explain what does inv(i) (j) signifies and how we use this to get the answer in the main function…
Thanks for such a great question…

It’s a table basically containing
I_b
I'_b
probably inv[0][bit] corresponds to first and inv[1][bit] corresponds to second. It means inversions resulting from (leaving the bit/flipping the bit)

@jafarbadour
We understand the complications in authoring a contest. Thanks for the awesome set of questions, I really loved the questions of this contest. :slight_smile:

2 Likes

Yeah sorry, my bad too. It wouldn’t work. But I think the code by setter is correct though. Because, what he is doing there, is that for each 0 in the current bit position counting the number of ones the preceded it and likewise for the flipped bit, counting zeros that proceeded each ones. This logically makes sense too.

1 Like

Haha it’s my code, I am both setter and editorial :smiley:
I was too frustrated after the contest ended, and I didn’t want to delay the editorials, so I was very depressed and not so conscious while writing because what happened was disappointing. I am sorry again.

4 Likes

@jafarbadour would be glad if you can provide link to similar questions for practice. I think one part of the editoral template on CC consists of providing link to similar problems for practice. Would be helpful if you can do that. :slight_smile: thanks for a nice problem regardless.

Almost any problem on xor share something similar with this task, I would suggest searching for “codeforces xor” in google and any task you would find may intersect with this one. Problems on xor usually follow very few patterns (especially at this level) so they are not very diverse. Something very common with xor is using trie. This question is almost doing the same thing that the Trie does. Especially here:

$Let’s say we have a vector v of length l and we are…$

4 Likes

If I submit some solutions to unrated questions of another division only during contest will my rating be affected?

No, It will not be affected.

1 Like

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

1 Like

I mentioned complexity in the edit. check it

3 Likes

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

5 Likes

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

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