PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given an array A of length N, decide whether the product of the bitwise XORs of all its elements lies in the range [L, R] or not.
EXPLANATION:
To solve this task, we’ll need to use a couple properties of bitwise XOR:
- x\oplus x = 0 for any integer x.
- If x and k are fixed, there’s exactly one integer y such that x\oplus y = k.
This y will, in fact, equal (x\oplus k).
Since we’re dealing with the product of bitwise XORs, if any bitwise XOR is 0, the entire product will be 0.
As noted at the start, the bitwise XOR can be zero only between two equal elements.
So, if any element appears twice (or more) in A, we can immediately say product will be 0, so the answer will be Yes if L = 0 and No otherwise.
There are many ways to check if A contains multiple copies of some element in \mathcal{O}(N\log N): for example you can sort A and compare adjacent elements, or you can insert all the elements of A into a set and check if the set has size N or not.
Next, let’s look at the case when all the elements of A are distinct, so the product of XORs is non-zero.
For each index i, there’s at most one other index j such that A_i\oplus A_j = 1.
This is because there’s exactly one other number y such that A_i \oplus y = 1, and elements of A are distinct so this y can appear at most once.
This means there are at most \frac N 2 pairs of elements in A whose bitwise XOR is equal to 1.
All elements are distinct, meaning that no bitwise XORs are equal to 0.
These two facts combined tell us that almost every bitwise XOR is \geq 2 - so their product gets very large very quickly.
In particular, if there are even 30 elements in the product, its value will exceed 2^{30} for sure - which is larger than the largest possible R.
This allows us to simply compute the product using brute force - either the array is small enough (as in, size \leq 10) that we obtain the actual product and can then check if it’s between L and R; or there are too many pairs in which case the product is certainly going to exceed R, and the answer is No.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, l, r; cin >> n >> l >> r;
vector <int> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
bool eq = false;
for (int i = 1; i < n; i++){
eq |= (a[i - 1] == a[i]);
}
if (eq){
if (l == 0) cout << "Yes\n";
else cout << "No\n";
return;
}
if (n > 10){
cout << "No\n";
return;
}
int prod = 1;
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
int v = a[i] ^ a[j];
prod *= v;
if (prod > r){
cout << "No\n";
return;
}
}
}
if (prod >= l){
cout << "Yes\n";
} else {
cout << "No\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, l, r = map(int, input().split())
a = list(map(int, input().split()))
dup = len(set(a)) < n
if dup:
print('Yes' if l == 0 else 'No')
continue
prod = 1
for i in range(n):
for j in range(i+1, n):
prod *= a[i] ^ a[j]
if prod > r: break
else:
continue
break
print('Yes' if l <= prod <= r else 'No')
.