PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: himanshu154
Tester: jay_1048576
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Familiarity with bitwise AND
PROBLEM:
Given an array A and an integer B, does there exist a subsequence of A whose bitwise AND equals B?
EXPLANATION:
First, recall the following property of bitwise AND:
That is, if x\ \&\ y = z, then both x and y will be supermasks of z (meaning any bit set in z will also be set in x and y).
This of course extends to the bitwise AND of several values as well:
If x_1 \ \&\ x_2\ \&\ \ldots \ \&\ x_k = y, then each x_i will be a supermask of y.
Let’s look at the above property from the perspective of the problem we want to solve.
We want to figure out whether there’s a subsequence of A such that its bitwise AND equals B.
That is, we want to know whether there exist indices 1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq N such that
Immediately, the first property tells us that each A_{i_j} will be a supermask of B.
So, we only care about those values in A that are supermasks of B.
Let S be the set of values in A that are supermasks of B.
Then, in fact S is the subsequence we’re looking for!
That is, if the bitwise AND of the values in S equals B, the answer is Yes.
Otherwise, the answer is No.
Why?
If the bitwise AND of S equals B, obviously the answer is Yes since we directly found a valid subsequence.
Now, suppose the bitwise AND of S doesn’t equal B.
Since every element of S has B as a submask, clearly their AND must also have B as a submask.
However, since it doesn’t equal B, the AND must also be a strict supermask of B — that is, there exists some bit k such that B doesn’t have k set; but every element of S does have k set.
Now, consider an arbitrary subsequence of A.
- If this subsequence includes an element outside S, clearly its bitwise AND cannot be B (by definition of S).
- If this subsequence is fully contained in S, then its AND will have bit k set for sure; and so cannot equal B anyway.
So, no subsequence has a bitwise AND of B, as claimed.
This gives a simple linear solution: find the bitwise AND of all supermasks of B, and check if it equals B or not.
TIME COMPLEXITY
\mathcal{O}(N) per testcase.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define rep(i,a,b) for(int i=a;i<b;i++)
void solve(){
int n,b;
cin>>n>>b;
vector<int> arr(n);
rep(i,0,n) cin>>arr[i];
int res_and=(1LL<<31)-1;
int cnt=0;
rep(i,0,n){
if((arr[i]&b) == b){
res_and = res_and & arr[i];
cnt++;
}
}
if(res_and == b && cnt>0){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
int32_t main() {
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("D:/Desktop/Test_CPP/CS2023_PON/CS2023_PON_3.in", "r", stdin);
freopen("D:/Desktop/Test_CPP/CS2023_PON/CS2023_PON_3.out", "w", stdout);
#endif
int t=1;
cin>>t;
while(t--){
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-6 << "ms\n";
return 0;
}
Tester's code (C++)
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007
void solve(int tc)
{
int n,b;
cin >> n >> b;
int a[n];
for(int i=0;i<n;i++)
cin >> a[i];
int c = INT_MAX;
for(int i=0;i<n;i++)
{
if((a[i]|b)==a[i])
c &= a[i];
}
if(c==b)
cout << "YES\n";
else
cout << "NO\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc=1;
cin >> tc;
for(int ttc=1;ttc<=tc;ttc++)
solve(ttc);
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, b = map(int, input().split())
have = 2**31 - 1
for x in list(map(int, input().split())):
if x&b == b: have &= x
print('Yes' if have == b else 'No')
