ENGXOR - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

Author: Saurabh Yadav
Tester: Suchan Park
Editorialist: William Lin

DIFFICULTY:

Simple

PREREQUISITES:

Bits, Basic Math

PROBLEM:

You are given an array A and you need to answer Q independent queries. For each query, you are given an integer P. You need to first output the number of i such that A_i \oplus P has an even number of set bits in its binary representation and then output the number of i such that A_i \oplus P has an odd number of set bits in its binary representation.

QUICK EXPLANATION:

Only the parity of the number of set bits in P matters, so we can reduce the queries to either P=0 or P=1. We can just precalculate the answer for both cases.

EXPLANATION:

Whenever we are working with bitwise operations (like in this problem), it is a good idea to consider the bits individually (separating the bits based on their position), since in bitwise operations, bits from different positions don’t interfere with each othet. Let’s make the problem easier: elements in A and P can only be either 0 or 1.

Under this case, the elements which have an even number of set bits will be 0 and the numbers which have an odd number of set bits will be 1.

To answer a query with a given P, it is pretty easy: If P=0, we first output the number of 0-s in A then output the number of 1-s in A. If P=1, we first output the number of 1-s in A (because those 1-s become 0-s in B) and then we output the number of 0-s in A (because those 0-s become 1-s in B). The only thing we need to do before answering the queries is to count the number of 0-s in A and the number of 1-s in A. Then, we can answer each query in constant time.

Let’s make this problem slightly harder: The elements in A are not restricted to be only 0 or 1, but P still has to be 0 or 1. What if P=0? In this case, A doesn’t change, so we first output the number of elements in A with an even number of set bits then output the number of elements in A with an odd number of set bits.

What if P=1? If x is some number and we xor it with 1, only the last bit of x will change. For example, if x=1001_2, then x \oplus 1 = 1000_2, and if x=10_2, x \oplus 1 = 11_2.

We can notice that the number of set bits in x either increases by 1 (when the last bit changes from 0 to 1) or decreases by 1 (when the last bit changes from 1 to 0). In either case, we notice that the parity of the number of set bits must change: if x has an even number of bits, then x \oplus 1 will have an odd number of bits, and if x has an odd number of bits, x \oplus 1 will have an even number of bits.

So, for queries with P=1, we first output the number of elements in A with an odd number of set bits and then output the number of elements in A with an even number of set bits. We just need to precalculate these two quantities before answer queries.

Let’s move on to the general case with no more constraint on P. Let’s consider all the set bits of P. Like in the case with P=1, each set bit of P will modify the corresponding bit in A_i after the xor, causing that bit to change.

In fact, if P has z set bits, then exactly z bits in A_i will change after the xor. Like in the previous case, each changed bit in A_i causes a change in the parity of the number of set bits in A_i. So if z=3, the parity of the number of set bits in A_i will change 3 times. Suppose that A_i had an odd number of set bits, then the final parity of the number of set bits of A_i will be odd -> even -> odd -> even.

Notice that 2 changes in the parity is equivalent to no change at all (odd -> even -> odd), so only the parity of z matters. So, our solution for the general case is very similar to the case where P can only be 0 or 1: if z=0, we pretend that P=0 and if z=1, we pretend that P=1.

The time complexity should be O(N+Q) or O((N+Q)\log A) depending on implementation.

IMPLEMENTATION:

As for finding the number of set bits in an integer, we can use the standard algorithm for finding the digits for a number in any base (in this case the base is 2). The code is below:

int numBits=0;
while(x>0) {
	numBits+=x%2;
	x/=2;
}

There are also library functions for certain languages to do this, like __builtin_popcount(x) for C++ and Integer.bitCount(x) for Java.

Also, as @kabirsingh2027 mentioned below, we can use __builtin_parity(x), which will return __builtin_popcount(x)%2.

HIDDEN TRAPS:

  • Make sure you use fast I/O, even the problem statement reminds you to do so! You can test if your input is fast enough with this problem. Make sure to not use “endl” for C++ (and don’t flush when unnecessary with all languages in general).

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
 
#define int long long int
#define endl "\n"
int32_t main()
{
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	cin>>t;
	while(t--)
	{
		int n,q;
		cin>>n>>q;
		int a[n];
		for(int i=0;i<n;i++)
			cin>>a[i];
		int odd=0,even=0;
		for(int i=0;i<n;i++)
		{
			int check=__builtin_popcount(a[i]);
			if( check%2==0)
				even++;
			else
				odd++;
		}
		while(q--)
		{
			int input;
			cin>>input;
			int odd1=odd,even1=even;
			int nodd=0,neven=0;
			int check1=__builtin_popcount(input);
			if(check1%2!=0)
			{
				
				odd1=even;
				even1=odd;
 
			}
			cout<<even1<<" "<<odd1<<endl;
		}
 
	}
	return 0;
}
Tester's Solution
#include <bits/stdc++.h>
 
const int BUFFER_SIZE = int(1.1e5);
 
char _buf[BUFFER_SIZE + 10];
int _buf_pos, _buf_len;
 
char seekChar() {
    if(_buf_pos >= _buf_len) {
        _buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
        _buf_pos = 0;
    }
    assert(_buf_pos < _buf_len);
    return _buf[_buf_pos];
}
 
bool seekEof() {
    if(_buf_pos >= _buf_len) {
        _buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
        _buf_pos = 0;
    }
    return _buf_pos >= _buf_len;
}
 
char readChar() {
    char ret = seekChar();
    _buf_pos++;
    return ret;
}
 
int readInt(int lb, int rb) {
    char c = readChar();
    int mul = 1;
    if(c == '-') {
        c = readChar();
        mul = -1;
    }
    assert(isdigit(c));
 
    long long ret = c - '0';
    int len = 0;
    while(!seekEof() && isdigit(seekChar()) && ++len <= 19) {
        ret = ret * 10 + readChar() - '0';
    }
    ret *= mul;
 
    assert(len <= 18);
    assert(lb <= ret && ret <= rb);
    return (int)ret;
}
 
void readEoln() {
    char c = readChar();
    assert(c == '\n');
    //assert(c == '\n' || (c == '\r' && readChar() == '\n'));
}
 
void readSpace() {
    assert(readChar() == ' ');
}
 
void run() {
    int N = readInt(1, 100000);
    readSpace();
    int Q = readInt(1, 100000);
    readEoln();
 
    int cnt[2] = {0, 0};
 
    for(int i = 0; i < N; i++) {
        int a_i = readInt(1, int(1e8));
        //if(i + 1 < N) readSpace(); else readEoln();
        readSpace();
        cnt[__builtin_popcount(a_i) % 2] += 1;
    }
    readEoln();
 
    for(int q = 0; q < Q; q++) {
        int p = readInt(1, int(1e5));
        if(q+1 < Q) readEoln();
        int c = __builtin_popcount(p) % 2;
        printf("%d %d\n", cnt[c], cnt[1-c]);
    }
}
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
 
    int T = readInt(1, 100);
    readEoln();
 
    while(T--) {
        run();
        if(T > 0) readEoln();
    }
    return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

void solve() {
	//input
	int n, q, c[2]={};
	cin >> n >> q;
	for(int i=0, a; i<n; ++i) {
		cin >> a;
		//add a to frequency array based on parity
		++c[__builtin_popcount(a)%2];
	}

	//queries
	for(int p; q--; ) {
		cin >> p;
		//determine the parity of p
		int z=__builtin_popcount(p)%2;
		//z is the 0s and z^1 (which flips z) is the 1s
		cout << c[z] << " " << c[z^1] << "\n";
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while(t--)
		solve();
}

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

24 Likes

hey william , my code is almost same as yours but only manages to get 30 points i dont understand why…

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--)
{

	int n,q;
	cin>>n>>q;
	
	int odd_count=0;
	int even_count=0;
	
	for(int i=0;i<n;i++)
		{	int k;
			cin>>k;
			if(__builtin_popcount(k)%2)
			{
				even_count++;
				
				}	
			else
				odd_count++;	
		}
	
	for(int i=0;i<q;i++)
	{
		int p;
		cin>>p;
		
		if(__builtin_popcount(p)%2!=0)
		cout<<even_count<<" "<<odd_count<<endl;	
		else
		cout<<odd_count<<" "<<even_count<<endl;	
			
	}
	

}

}

2 Likes

Look at the hidden traps
Actually, I didn’t specify that you should also not use “endl”. Let me add that.

4 Likes

why it is getting tle?

    #include <iostream>

    int main() {
    	std::ios_base::sync_with_stdio(false);
    	std::cin.tie(nullptr);
    	int t;
    	std::cin >> t;
    	while (t--) {
    		int n;
    		int q;
    		std::cin >> n >> q;
    		int arr[n];
    		for (int i = 0; i < n; i++)
    			std::cin >> arr[i];
    		while (q--) {
    			int p;
    			std::cin >> p;
    			int cntOdd = 0;
    			int cntEven = 0;
    			for (int i = 0; i < n; i++) {
    				int x = p ^arr[i];
    				if (__builtin_parity(x))
    					cntOdd++;
    				else
    					cntEven++;
    			}
    			std::cout << cntEven << " " << cntOdd << "\n";
    		}
    	}
    	return 0;
    }

This is O(nq) which is too big for the constraints.

In my solution, after changing endl to "\n" and adding ios_base::sync_with_stdio(false);cin.tie(NULL);, the solution got an A.C.
Anyways, here’s mine -
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>

        typedef long long int ll;
        #define test int t; cin >> t; while(t--)
        #define MOD 1000007
        using namespace std;



            ll countSetBits(ll n) 
            { 
                ll count = 0; 
                while (n) { 
                    n &= (n - 1); 
                    count++; 
                } 
                return count; 
            } 

        int main (){
          ios_base::sync_with_stdio(false);
          cin.tie(NULL);
        test {


        		ll n,q;
        		cin >> n >> q;
                ll count=0;
        		ll a[n];
        		for(ll i=0;i<n;i++){
        			cin >> a[i];
        			if(countSetBits(a[i])%2==1){
        				count ++;
        			}
        		
        		}
        		for(ll i=0;i<q;i++){
        			ll p;
        			cin >> p;
        			if(countSetBits(p)%2==0){
        			    cout << n-count << " " << count << "\n";
        			}
        			else {
        			    cout << count << " " << n-count << "\n";
        			}
        		}
        	}
        	return 0;
        }

My solution to engxor https://www.codechef.com/viewsolution/30494808

1 Like

Thanks. I got it where I missed it.
Can you give me some tips that how I can get better in competitive programming? As not much sign of improvement is seen since I have started doing it.
Thanks in advance!

Instead of __builtin_popcount(x) we can directly use __builtin_parity(x)
basically if f(N) represents number of set bits in binary representation of N, then
f(N xor K) = f(N) xor f(K)
where f(x) is __builtin_parity(x), a built-in function in C++.

5 Likes

Wow, didn’t know that, thanks!

1 Like

Why this code got TLE in subtask 2? My approach was little different.

import java.util.*;
import java.lang.*;
import java.io.*;


class Codechef
{
	public static int parity(int x) {
    
    int y;
    y = x ^ (x >> 1);
    y = y ^ (y >> 2);
    y = y ^ (y >> 4);
    y = y ^ (y >> 8);
    y = y ^ (y >> 16);
    
    return y & 1;
}

public static void main (String[] args) throws java.lang.Exception
{
	// your code goes here
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int t = Integer.parseInt(br.readLine().trim());
	while(t-- > 0) {
	    
	    Queue<Integer> queue = new ArrayDeque<>();
	    
	    String[] s1 = br.readLine().trim().split(" ");
	    int n = Integer.parseInt(s1[0]);
	    int q = Integer.parseInt(s1[1]);
	    
	    int[] a = new int[n];
	    int[] p = new int[q];
	    
	    String[] s2 = br.readLine().trim().split(" ");

	    for(int i = 0; i < n; ++i) {
	        a[i] = Integer.parseInt(s2[i]);
	    }
	    for(int i = 0; i < q; ++i) 
	        queue.add(Integer.parseInt(br.readLine().trim()));
	    
	    int even = 0, odd = 0;
	    int temp = queue.remove();
	    
	    for(int i = 0; i < n; ++i) {
	        int par = parity(a[i] ^ temp);
	        if(par == 0)
                ++even;
            else    
                ++odd;
	        if(i == n - 1 && !queue.isEmpty()) {
	            i = -1;
	            System.out.println(even + " " + odd);
	            even = 0;
	            odd = 0;
	            temp = queue.remove();
	        }
	    }
	    if(queue.isEmpty())
	             System.out.println(even + " " + odd);
	}
}

}

*** HEY I M HIMANSHU I ALSO TEXTED IN YOU IN CODEFORCES
MY QUESTION IS IN CASE OF FOR LOOP CAN WE USE WHILE LOOP?

for(int p; q–; ) {
cin >> p;
//determine the parity of p
int z=__builtin_popcount§%2;
//z is the 0s and z^1 (which flips z) is the 1s
cout << c[z] << " " << c[z^1] << “\n”;
}

@tmwilliamlin why shouldn’t we use endl?

I don’t understand this part at all!

yes

try fast output for java (printwriter)

We make a simple version of the problem where all elements can only be 0/1.

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main(String[] args) {
FastReader reader = new FastReader();
PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
//BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
int t;
try {
t = reader.nextInt();
for (int i = 0; i < t; i++) {
int n, q;
n = reader.nextInt();
q = reader.nextInt();
int a[] = new int[n];
int even1s = 0, odd1s = 0;
for (int j = 0; j < n; j++) {
a[j] = reader.nextInt();
int setBits = countSetBits(a[j]);
if (setBits % 2 == 0) {
even1s++;
} else {
odd1s++;
}
}
for (int j = 0; j < q; j++) {
int p = reader.nextInt();
int setBits = countSetBits§;
if (setBits % 2 == 0) {
//writer.write();
writer.write(even1s + " " + odd1s + “\n”);
writer.flush();
} else {
writer.write(odd1s + " " + even1s + “\n”);
writer.flush();
}
}
}
} catch (Exception e) {
e.printStackTrace();
}
}

private static int countSetBits(int num) {
    int setBits = 0;
    while (num != 0) {
        num = num & (num - 1);
        setBits++;
    }
    return setBits;
}

static class FastReader {
private BufferedReader br;
private StringTokenizer st;

public FastReader() {
    br = new BufferedReader(new InputStreamReader(System.in));
}

public String next() {
    while (st == null || !st.hasMoreElements()) {
        try {
            st = new StringTokenizer(br.readLine());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    return st.nextToken();
}

public int nextInt() {
    return Integer.parseInt(next());
}

}
}
I used PrintWriter and Fast I/O in java still getting TLE in second part

Here’s my submission for ENGXOR. AC in one go :smile:

#include <iostream>
using namespace std;



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int testCases = 0;
	cin >> testCases;
	while(testCases--){
		int noOfElements = 0;
		int noOfQueries = 0;
		cin >> noOfElements >> noOfQueries;
		int countOfParity[2];
		countOfParity[0] = countOfParity[1] = 0;
		for(int i = 0 ; i < noOfElements ; ++i){
			int temp;
			cin >> temp;
			int noOfBits = __builtin_popcount(temp);
			if(noOfBits%2 == 0) ++countOfParity[0];
			else ++countOfParity[1];
		}
		while(noOfQueries--){
			int P;
			cin >> P;
			int noOfBitsP = __builtin_popcount(P);
			if(noOfBitsP%2 == 0){
				cout << countOfParity[0] << " " << countOfParity[1] << '\n';
			}
			else{
				cout << countOfParity[1] << " " << countOfParity[0] << '\n';
			}
		}
	}
	return 0;
}

Good explanation

1 Like