PROBLEM LINK:
Author: Shahjalal Shohag
Tester: Ildar Gainullin
Editorialist: Rajarshi Basu
DIFFICULTY:
Easy
PREREQUISITES:
Observation
PROBLEM:
You are given an integer sequence A_1, A_2, \ldots, A_N. For any pair of integers (l, r) such that 1 \le l \le r \le N, let’s define \mathrm{OR}(l, r) as A_l \lor A_{l+1} \lor \ldots \lor A_r. Here, \lor is the bitwise OR operator.
In total, there are \frac{N(N+1)}{2} possible pairs (l, r), i.e. \frac{N(N+1)}{2} possible values of \mathrm{OR}(l, r). Determine if all these values are pairwise distinct.
- N \leq 10^5
- 0 \leq A_i \leq 10^{18}
EXPLANATION:
Brief Explanation
- If number of elements is more than \log_2 10^{18} \approx 62 then answer is NO.
- Else just bruteforce all possible ranges.
Some initial thoughts
The question involves bitwise operators. When you see bitwise operators involved, it’s safe to say there might be something to do with … well… bits. Further, it feels like the number of possible different values of subarray OR cannot be too many, and seems to be much lesser than O(n^2) in any case. Maybe this can be explored further?
What makes a number important
Let us say we have some range of numbers A[L \dots R]. Let us say we add another number, in particular A[R+1] (so our final range is A[L \dots R+1]). When will the OR value of this range be different than the previous A[L \dots R] range? When A[R+1] adds some ”new information” right?
What is this new information?
Well, this new information is basically some bit i that was not set in V_1 = A[L] \vee A[L+1] \vee \dots \vee A[R]. Is this true? What does this mean for the problem? Does it hint towards a solution? Think!
Main Observation
Part 1
Let there be two indices i and j such that A[i] \vee A[j] = max(A[i],A[j]). You can think of this meaning that all of the bits set in A[j] is also set in A[i], or vice versa, for some i,j. In such a scenario, the solution is not possible. Here’s why.
- Let’s assume that i < j.
- Now consider V_1 = (A[i] \vee A[i+1\ \vee A[i+2] \vee \dots \vee A[j-1]).
- Now consider V_2 = V_1 \vee A[j]
- We know that each bit k set in A[j] is also set in A[i], and therefore in V_1. Thus, from there we get that V_2 = V_1.
How do we utilise this to simplify the problem? Move on to Part 2 if you can’t figure it out.
Part 2
There are only 62 bits for a number till 10^{18} !!
Full Solution
- If number of elements is more than \log_2 10^{18} \approx 62 then answer is NO.
- Else just bruteforce all possible ranges.
SOLUTIONS:
Setter’s Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const long long M = 1e18;
long long a[N];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
assert(1 <= t && t <= 300);
int sum = 0;
while (t--) {
int n; cin >> n;
assert(1 <= n && n <= 100000);
sum += n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
assert(0 <= a[i] && a[i] <= M);
}
if (n > 60) {
cout << "NO\n";
continue;
}
set<long long> se;
bool ok = true;
for (int i = 1; i <= n; i++) {
long long cur = 0;
for (int j = i; j <= n; j++) {
cur |= a[j];
if (se.find(cur) != se.end()) {
ok = false;
break;
}
se.insert(cur);
}
if (!ok) break;
}
if (ok) cout << "YES\n";
else cout << "NO\n";
}
assert(1 <= sum && sum <= 300000);
return 0;
}
Tester’s Code
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector <ll> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n >= 100) {
cout << "NO\n";
} else {
set <ll> q;
for (int i = 0; i < n; i++) {
ll x = 0;
for (int j = i; j < n; j++) {
x |= a[j];
q.insert(x);
}
}
if (q.size() == n * (n + 1) / 2) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
}