NILXOR - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Akshit Monga
Preparer: Tejas Pandey
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh

DIFFICULTY:

2001

PREREQUISITES:

Bitwise operations

PROBLEM:

You are given N and X. Find the number of integers K such that 0 \leq K \lt N and ((N \oplus K) \And X) = 0.

EXPLANATION

Since this task deals with bitwise operations, it makes sense to look at things bit by bit.

If the binary representation of a number y has a 1 in the i-th position, we say the i-th bit is set in y.

Now, we want the bitwise and of N\oplus K with X to be 0. This means that if a bit is set in X, it will be set in K if and only if it is set in N. In other words, if some bit of X is set, there is exactly one choice for such a bit in K.

After this, we apply a classical technique when counting things that must be lexicographically smaller than something else. Iterate over the positions, and fix the one that is the first to be strictly less, then we have complete freedom in all following positions.

That is, iterate bits from 30 down to 0. Suppose we are currently at the i-th bit. We will assume that the bits from 30 to (i+1) of both N and K are equal, and the i-th bit of K is strictly less than the i-th bit of N (of course, note that this is only possible when the i-th bit of N is 1, and the i-th bit of X is not 1).

Now, bits 0 to i-1 are totally free (except for the restriction on set bits of X mentioned before), and each of these have 2 choices (can be 0 or 1). So, if there are c such free bits, we add 2^c to the answer.

The final algorithm looks like this:

  • Iterate i from 30 down to 0.
  • If the i-th bit is either set in X or not set in N, do nothing
  • Otherwise, count the number of bits from 0 to i-1 that are not set in X. If this number is c, add 2^c to the answer.

This can be implemented in \mathcal{O}(\log N) by maintaining the running sum of bits that are not set in X; however a more naive implementation in \mathcal{O}(\log^2 N) will still be fast enough.

TIME COMPLEXITY:

\mathcal{O}(\log N) per test case.

CODE:

Setter's code (Python)
t=int(input())
for _ in range(t):
    n,x=map(int,input().split())
    ans=p=0
    for i in range(0,30):
        if not x&(1<<i):
            if n&(1<<i):ans+=(1<<p)
            p+=1
    print(ans)
Tester's code (C++, tabr)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, x;
        cin >> n >> x;
        int ans = 0;
        for (int i = 29; i >= 0; i--) {
            if (~x & (1 << i)) {
                ans *= 2;
                if (n & (1 << i)) {
                    ans += 1;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

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

	int t; cin >> t;
	while (t--) {
		int n, x; cin >> n >> x;
		int ans = 0, ct = 31 - __builtin_popcount(x);

		for (int bit = 30; bit >= 0; --bit) {
			if ((x >> bit) & 1) continue;
			--ct;
			if ((~n >> bit) & 1) continue;

			// Let this be the first bit that is strictly less than n
			ans += 1 << ct;
		}
		cout << ans << '\n';
	}
}
1 Like

https://www.codechef.com/viewsolution/71664599
https://www.codechef.com/viewsolution/71649892
https://www.codechef.com/viewsolution/71637434
https://www.codechef.com/viewsolution/71638559
https://www.codechef.com/viewsolution/71638559
just randomly selected some Indian account solutions from the top 20
Why would anyone give contests on codechef if this is a regular practice

9 Likes

These people are a disgrace. But you know what’s worse, codechef doesn’t even do a regular plag
check or maybe cc’s plag checker is just dumb.
Req to cc : stop updating platform and adding stupid AI explainers and just do a strict plag check and then update ratings after removing cheaters, we can wait.

9 Likes

I dont even hope to get reply from any official regarding this.
codeforces >>>>>>>>>>>>>>>>>>>>

5 Likes

cout << dfs(39, 1) - 1 << endl;
people have simply copied this line without even making sense
it shud be 31 / 32 y wud anyone use 39
easy to catch

Could you please make a video on this?
I am having trouble understanding the solution.
Thanks.

2 Likes

bro this contest are not rated for 3star coder.
so don’t worry

Can’t agree more.
codeforces>>>>>>>>>>>>>>> +1

Can you please provide me some random test case for this problem???

Suppose if at some ith bit position we have 1 at that bit position in X , then for ((N⊕K)&X)=0 to hold, (N⊕K) must be 0 at ith bit position, So this will depend on bit of N at that position. If ith bit of N is 1, then we should have ith bit in K to be 0. Similarly if ith bit of N is 0, then we should have ith bit in K to be 1. So there is more than one choice for K at that bit position. Or am i missing something?

Please explain agian with example … :pray: :pray:

Please explain again with example and detailed step wise procedure :pray: :pray: :pray

Your analysis is correct, you’re only missing the fact that N is given as part of the input.

So, if the i-th bit of N is zero (and the i-th bit of X is set), that forces the i-th bit of K to be 1 for any valid K — there cannot be any valid K whose i-th bit is 0. This is what I mean when I say that there is exactly one choice for these bits. That choice might be different for different bits, but for a given bit it’s still only one choice, i.e, they are fixed.

This is in contrast to bits that are not set in X - for these bits, there can be valid K such that this bit is either 0 or 1. This is what the solution counts.

can u please tell
what is this classical technique in solution
After this, we apply a classical technique when counting things that must be lexicographically smaller than something else. Iterate over the positions, and fix the one that is the first to be strictly less , then we have complete freedom in all following positions.

@iceknight1093 @abhi_kant @thunder_flame

I am not getting, how the case K<N is getting covered in the editorial and in the solutions.
I mean how are we checking that condition?

We will have 2 choices whenever the bit is not set in X, that means if I have 3 “0” bits in X, then my answer would be 8, but I am not getting how are you handling the case K<N