PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
1823
PREREQUISITES:
Familiarity with bitwise OR
PROBLEM:
You’re given an array A containing at least two distinct elements, and an integer X.
For an integer 0 \leq Y \leq X, define the array B as B_i = A_i \mid Y.
Find the largest Y such that B consists of at least two distinct elements.
EXPLANATION:
Since the operation we’re dealing with is bitwise OR, it helps to look at things bit-by-bit.
First, a useful definition: we say a bit b is set in the binary representation of integer x if the binary representation of x contains 2^b.
For example, 9 = (1001)_2 = 2^0 + 2^3 has bits 0 and 3 set, while bits 1, 2, 4, 5, 6, \ldots are not set.
Suppose we pick a Y and compute the array B, and there are two unequal elements; say B_i \neq B_j.
Then, in particular the binary representation of B_i and B_j must differ.
That is, there must exist a bit b which is set in the binary representation of B_i but not in B_j, or vice versa.
Without loss of generality, let’s say b is set in B_i and unset in B_j.
Then, we can observe the following:
- Y cannot have bit b set (otherwise it would be set in B_j = A_j \mid Y)
- This means A_i must’ve had bit b set, and A_j must’ve had it unset.
This tells us that for any valid Y, there will exist a bit b such that:
- b is unset in Y,
- Some element of A has this bit set, and
- Some element of A has this bit unset
Conversely, any Y that has such a bit b can easily be seen to satisfy the condition.
So, let’s fix the value of b and try to find the largest Y we can with respect to it; call this Y_b.
The answer is the maximum value of Y_b across all b.
Note that if b is such that:
- Every element of A has b set; or
- Every element of A has b unset
then b must be ignored, as per our rules above.
For a fixed b, this can easily be checked in \mathcal{O}(N) by iterating across all the elements.
Now the question is, how to find Y_b for a fixed b?
That can be done greedily.
- Iterate over bits from largest to smallest, i.e, from 29 down to 0.
- Initially, let Y_b = 0.
- Then, when processing bit i,
- If i = b, do nothing. This will ensure that Y_b doesn’t have bit b set, as required.
- Otherwise, if Y_b + 2^i \leq X, add 2^i to Y_b.
This way, we ensure that we never exceed X, while also making Y_b as large as possible.
So, for each b:
- We first check whether it is possibly valid, i.e, some element of A has it set and some other element has it unset.
This is done in \mathcal{O}(N). - If it’s valid, we construct Y_b using the above algorithm. This is done in \mathcal{O}(30).
Since we do this for each bit from 0 to 29, the overall runtime is \mathcal{O}(30\cdot N + 30^2) which is good enough.
TIME COMPLEXITY
\mathcal{O}(30\cdot N + 30^2) per test case.
CODE:
Setter's code (C++)
#pragma GCC optimization("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(int x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=200200;
void solve(){
ll n,x; cin>>n>>x;
vector<ll> a(n);
for(auto &it:a){
cin>>it;
}
ll smallest=0;
set<ll> need;
for(ll i=29;i>=0;i--){
ll found=0;
for(auto it:a){
found+=min(1ll,it&(1<<i));
}
if(found>=1 and found!=n){
need.insert(i);
}
}
assert(need.size()>=1);
smallest=*need.begin();
ll ans=0,done=0;
for(ll i=29;i>=0;i--){
if(done or smallest<i){
if(ans+(1<<i) <= x){
ans+=(1<<i);
}
else if(need.count(i)){
done=1;
}
}
}
vector<ll> b=a;
for(auto &it:b){
it|=ans;
}
sort(all(b));
assert(b[0]!=b[n-1]);
cout<<ans<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Editorialist's code (Python)
for _ in range(int(input())):
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for b in range(30):
ct = 0
for y in a: ct += (y >> b) & 1
if ct == 0 or ct == n: continue
cur = 0
for bit in reversed(range(30)):
if bit == b: continue
if cur + (1 << bit) > x: continue
cur += 1 << bit
ans = max(ans, cur)
print(ans)