PROBLEM LINK:
Setter- Priyanshi Gupta
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey
DIFFICULTY:
EASY
PRE-REQUISITES:
Goldbach’s Conjecture , Frequency array concept, Properties of XOR.
PROBLEM:
Given an array A of N numbers, we need to tell number of pairs of indices (i,j) such that -
- 1 \le i < j \le N (1 based indexing)
- A_i \oplus A_j can be written as sum of 2 prime numbers of same parity.
QUICK-EXPLANATION:
Key to AC- Deducing 2 facts-
1. XORing numbers of same parity always results in even numbers. And adding prime numbers of same parity results in even numbers as well.
2. Correlating above to Goldbach’s conjecture which says any even number >2 can be represented as a sum of 2 primes.
Deducing above 2 was was the main turning point, and difference between a quick AC and complete cluelessness.
Quick Explanation- Focus on what the question says. It first says that, A_i \oplus A_j must be representable as a sum of prime numbers of same parity. Its basic math that adding two numbers of same parity results in a sum of even parity (i.e. Odd+Odd=Even. Even+Even=Even). Also, the same rule holds for XOR.
Appplying Goldbach’s conjecture, the question reduces to find how many pairs (i,j) exist such that-
- Their XOR is even.
- Their XOR is greater than 2.
For XOR being even, we check only among pairs with same parity. For XOR being greater than 2, we first find number of all possible even XOR values, and then reduce count of XORs with value 2 and 0. This can be done easily via frequency array.
EXPLANATION:
The explanation will have a single section explaining editorialist’s solution. Some proofs are left as in exercise to reader - their answers can be found in my bonus corner at the end of editorial. Try to read the editorial in a way to capture the thought process going in mind of a coder, because often we all know and are aware of things but fail at application in correct form. I assume you are thorough with basic properties of XOR. Please read them under pre-requisites if its not the case!
Editorialist’s Solution-
Lets first discuss the solution of first sub-task for formality. The idea of first subtask is to use 2 nested loops, and try out all the possible \frac{N*(N-1)}{2} values of i and j. If their XOR is even and greater than 2, add 1 to answer.
Now, before moving towards the full solution, grasp the 3 rules I say below. If having trouble, try to prove them or check out proofs in the bonus corner below. Then, proceed once you have proper clarity about those.
1. Only the rightmost bit (i.e. Least-significant bit or LSB) determines whether a number is odd or even.
2. Using above rule, conclude that XOR of numbers of same pairty is always even. (i.e. Even \oplus Even=Even and Odd \oplus Odd=Even)
3. Read Goldbach’s Conjecture, which says, " that every even integer greater than two is the sum of two prime numbers.". Do NOT try to prove it. This conjecture is still unproven and its proof is one of mysteries, but the results have been verified to hold true for numbers even larger than 4*{10}^9. Hence, it holds good in the range of input which we have.
With above 3, we can get a hint of implementation in mind. We need a count of numbers which are odd, and which are even (so that their XOR is always even).
After that, we have to check that the equivalent XOR is greater than 2. If it is, then by Goldbach’s conjecture, any even number greater than 2 satisfies our condition of being a sum of 2 primes of same parity. Now, this part is where most of contestants face problem - usually because they never did a similar problem before.
Newbies get overwhelmed by “Ok its easy to make sure that XOR is even, but how do I assure that its greater than 2 and include only proper indices in my answer?!”
The answer is simple, dont! The proper methodology is to, first find the answer including repetitions and pairs with XOR \le 2 as well, and later subtract irrelevant ones from answer. (You can find a note about it in point 3. of my corner.) Making sure that XOR is >2 on the run is difficult. Instead, first just count how many pairs (i,j) are there such that A_i \oplus A_j is even. That is easy, right? Make it easier, for now, forget about restriction of 1 \le i < j \le N, just find any pair (i,j) such that 1 \le i,j \le N. Any pair will do, no constraints on i and j. Can you do that, if you are given the array A and know how many numbers in it are odd and how many numbers are even? (Check out tab below to see how if cannot).
Click to view
Since there is no restriction on (i,j), we can simply follow below-
for(i=0;i< n;i++)
{
if(arr[i]%2==1)//If number is odd
ans+=odd;//Odd= number of odd elements in array
else //If number is even
ans+=even;//even =number of even numbers in array.
}
The logic is that, if my A_i is odd, then I have odd (odd= number of odd elements in array) choices of indices to pick currently such that the resultant XOR is even, hence I add odd to answer. If A_i is even, then I have even choices of indices to pick, where even represents number of even number in array as shown in above code. I add that to answer.
Now, we have the answer in crude form, what we have to do is to account for repetition of pairs (we counted (2,1) and (1,2) differently, which makes our answer twice the expected one), which can be easily done by halving the answer in the end.
First, we have to take care of cases when XOR comes out to be 2 or 0 (i.e. even number \le 2). This is also simple! For this, maintain a frequency array, and now count how many times each number occurs.
Now, think to yourself, for every element in array A_i, how many choices do I have to choose j such that 1 \le i,j \le N and A_i \oplus A_j=2 ? Lets use b to represent all numbers such that b \oplus A_i=2. We find that b=A_i \oplus 2. (Proof given in tab below). Hence, all we have to do is to subtract the count of numbers with value A_i \oplus 2 to account for numbers having XOR=2!!
Click to view
We have-
b \oplus A_i=2
Xoring both sides with A_i-
b \oplus A_i \oplus A_i=2 \oplus A_i
Xor can be done in any order. Also, its known that, for any number K, K \oplus K=0. Hence, the above becomes-
b \oplus (A_i \oplus A_i)=2 \oplus A_i
\implies b \oplus 0=2 \oplus A_i
\implies b = 2 \oplus A_i
This also means that b is unique for a given A_i
Similarly, to account for numbers with XOR 0, we think of how many choices do I have to choose pairs (i,j) under same conditions (as above) such that A_i \oplus A_j=0. It is very easy to see that, if we use b to represent choices of numbers such A_i \oplus b=0, then this will imply that b= A_i. Hence, we simply reduce frequency of A_i from our crude answer.
(Check out above proof and try to follow exact guidelines to derive this, if in confusion how we concluded this. The steps to be followed are exact same!).
In the end, as I mentioned above, after accounting for XORS resulting in 2 and 0, we simply halve the answer to get the final answer to print 
.
As an exercise, try to write down an implementation of above idea in pen and paper. A code to compare your implementation with is given below as answer-
One warning though, make sure to declare your frequency array larger than size 1000001 so that you dont get out of bounds when checking for count of A_i \oplus 2
Click to view
//Odd^Odd=Even. Even ^ Even=Even. ^=XOR operation.
for(i=0;i<n;i++)
{
if(arr[i]&1)ans+=odd;
else ans+=even;
ans-=freq[arr[i]^2];//Remove count of elements by which XOR is 2
ans-=freq[arr[i]];//Remove count of elements by which XOR is 0.
}
cout<<(ans>>1)<<endl;//Divide answer by 2 as we doubly counted. i.e. we took (1,2) different
//from (2,1).
//Hence, half the answer out for exact required number.
SOLUTION
The respective codes are also pasted in tabs below in case the links do not work. This is for convenience of readers, so that they can copy paste it to whichever IDE or editor they are comfortable reading it in and immediately have access to the codes.
Author’s solution can be found here.
Click to view
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
int a[123456],b[1234567];
int cnt[123];
int main(){
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int i;
ll ans=0;
// b[i] counts occurence of i so far.
rep(i,1234567){
b[i]=0;
}
// cnt counts number of even and odd numbers so far.
rep(i,5){
cnt[i]=0;
}
// Using goldbach principle all even numbers more than 3 can be written as sum
// of primes (Since number is even, both primes should have same parity).
// Now in odd case, parity will always be different.
rep(i,n){
cin>>a[i];
// cnt of same parity numbers, becuase xor with them will give even number.
ans+=cnt[a[i]%2];
// but we dont want it to zero
ans-=b[a[i]];
// but we dont want it to two
ans-=b[(a[i]^2)];
b[a[i]]++;
cnt[a[i]%2]++;
}
cout<<ans<<endl;
}
return 0;
}
Click to view
/*
*
********************************************************************************************
* AUTHOR : Vijju123 *
* Language: C++14 *
* Purpose: - *
* IDE used: Codechef IDE. *
********************************************************************************************
*
Comments will be included in practice problems if it helps ^^
*/
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
#ifdef JUDGE
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
srand(time(NULL));
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int i,arr[n],freq[1100001]={0};//Frequency array
for(i=0;i<n;i++)
{
cin>>arr[i];
freq[arr[i]]++;//update frequency of number
}
long long odd=0,even=0,ans=0;
for(i=0;i<n;i++)//Count how many odd and even numbers are there
{
if(arr[i]&1)
odd++;
else
even++;
}
//Odd^Odd=Even. Even ^ Even=Even. ^=XOR operation.
for(i=0;i<n;i++)
{
if(arr[i]&1)ans+=odd;
else ans+=even;
ans-=freq[arr[i]^2];//Remove count of elements by which XOR is 2
ans-=freq[arr[i]];//Remove count of elements by which XOR is 0.
}
cout<<(ans>>1)<<endl;//Divide answer by 2 as we doubly counted. i.e. we took (1,2) different from (2,1).
//Hence, half the answer out for exact required number.
}
return 0;
}
Time Complexity=O(N)
Space Complexity=O(N)
CHEF VIJJU’S CORNER 
1. Proof Only LSB determines pairty.
Click to view
Represent the number in Binary. Let me represent bit at i'th index from right by b_i and used 0-based indexing. Hence, LSB is represented by b_0. Now, recall how do we convert a number from binary to decimal. Say I give you (1101)_2 and ask to write its decimal equivalent, what will you do? You will say, that the decimal number is equal to (2^0+2^2+2^3=8+4+1=13). Now, stop there and observe one thing. Except 2^0, all numbers are even! And guess where this 2^0 comes from? Yes, LSB!
Now we know that Even+Odd=Odd and Even+Even=Even. If LSB is 1, we will have to add 2^0=1 in the answer. All of the rest numbers will be of form 2^i and have i\ge 1 and hence be even. Hence, only LSB will determine if an odd number (i.e. 1) will be added to current sum (which is even) or not, and hence determines parity.
2. XOR of same parity is always even.
Click to view
Parity depends only on the LSB. Lets consider 2 cases, when LSB of both numbers if 1, and when it is 0 for both of them.
Take below 2 numbers as example for first case-
1010101 \oplus 10001.
We only care about LSB as we are interested in pairty. In this case, it’d be 1 \oplus 1=0. Similarly, in other case, when LSB of both is 0, it’d be 0 \oplus 0=0.
If numbers are not of same parity, the LSB of one number will be 1 and of other will be 0. XORing them, we will find LSB of result to be 1 \oplus 0= 0 \oplus 1=1 which is odd.
3. LoEE-
Click to view
Law of Easy Elimination: This is a methodology coders follow when they see following properties in answer-
- Calculating answer at once, is difficult. However, a crude answer, which may include invalid pairs and/or repetitions can be easily found.
- It is easier to eliminate the invalid pairs and repetitions from crude answer, than to acccount for them on the run at once while calculating answer.
In this methodology, we first calculate the crude answer first, and then proceed to find final answer by subtracting invalid pairs and/or repetitions.
4. Related problems - The only reason newbies are not able to solve problems on frequency array topic is because of lack of practice. Practice these problems till the process becomes completely mechanical and intuitive for you.
-
AVGPR - Another question on Frequency array. You can find more problems in my editorial of this problem