PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: alve2000
Testers: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Familiarity with bitwise operations
PROBLEM:
You’re given an array A of length N.
Answer Q queries on it:
- You’re given X and K.
At most K times, choose a subarray of A and replace every A_i in it with A_i\oplus X. - Find the maximum possible value of the bitwise AND of the final array.
EXPLANATION:
First, let’s figure out how to solve a single query of (X, K).
Since our aim is to maximize the bitwise AND of the resulting array, it’s better to attain higher bits as much as possible.
A_i and X being \leq 10^6 means we care only about the first 20 bits.
Let’s define an N\times 20 boolean array B, where B_{i, j} if 1 if A_i has the j'th bit set, and 0 otherwise.
Then, for any bit b,
- If X doesn’t have b set, we cannot change any of the B_{i, b} values.
- If X does have b set, performing the XOR operation on some subarray [L, R] will simply flip the values of B_{i, b} for each L \leq i \leq R.
In terms of B, note that the bitwise OR of A is simply the sum of 2^b across all bits b such that B_{i, b} = 1 for every i.
This is simply a way of stating that “the bitwise AND of A will have a bit set in it if and only if this bit is set in every element of A”.
Now, let’s consider a fixed bit b.
If the current bit b isn’t set in X, we know how to check whether it’ll be set in the answer or not (every B_{i, b} should be 1).
If instead the current bit b is set, we are now able to modify the b'th column of the grid B by flipping some ranges of values within it.
Our aim is to make every value within the b'th column equal 1.
Suppose the b'th column has C_b contiguous blocks of zeros.
Then, we need at least C_b moves to make them all contain 1.
So, if K \lt C_b, it’s impossible to set every B_{i, b} to 1, and b cannot be present in the answer.
If K \geq C_b however, it’s obviously possible to perform the necessary flips, and we’re definitely able to set b in the answer.
On the other hand, note that the set of positions that need to be flipped is now uniquely determined.
So, for any bits lower than b (that are also set in X), they can be present in the answer if and only if the set of positions needed to be flipped is exactly the same as that of bit b.
This gives us a rather direct algorithm:
- For every bit that’s not set in X, see whether it’ll be set in the answer or not.
- Among the bits that are set in X, let b be the highest one with C_b \leq K.
- For every bit b_2 set in X that’s smaller than b, check whether the set of positions that need to be flipped in it is the same as the set of positions that need to be flipped in b.
This is really just a check of whether the b-th and b_2-th columns of B are equal.
If implemented directly, the above algorithm takes \mathcal{O}(20\cdot N) or \mathcal{O}(20^2 \cdot N) time.
This is obviously too slow to do for each query, but optimizing it isn’t too hard since very little changes between queries.
In particular,
- To deal with bits that aren’t set in X, we need to know whether they’re set in every element of A or not.
This information can be precomputed and looked up in constant time. - Among the bits that are set, we want to find the highest one that satisfies C_b \leq K.
The C_b values don’t change across queries, so those can be precomputed too. - Finally, for bits lower than b, we want to check whether their column is equal to the b-th column of B.
The columns themselves don’t change, so once again, simply precompute the results of all pairwise comparisions of them.- This can be done in \mathcal{O}(20^2 N) time by directly comparing each pair, \mathcal{O}(20N\log 20 + 20^2) time using sorting, or even \mathcal{O}(20 N) time using hashing
With all this precomputation, each query can now be answered by just enumerating bits from largest to smallest and looking up precomputed values, eliminating the \mathcal{O}(N) part from the complexity entirely.
TIME COMPLEXITY:
\mathcal{O}(20\cdot (N + Q)) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+2;
int a[N];
vector<array<int,2>> rng[20];
bool similar[20][20];
void solve() {
int n,q;
cin >> n >> q;
for(int i = 0; i < 20; i++) {
rng[i].clear();
for(int j = 0; j < 20; j++)
similar[i][j] = 0;
}
for(int i = 0; i < n; i++)
cin >> a[i];
for(int k = 0; k < 20; k++) {
for(int i = 0; i < n; i++) {
if(((1 << k) & a[i]) == 0) {
int l = i;
while(i < n and ((1 << k) & a[i]) == 0) i++;
i--;
rng[k].push_back({l,i});
}
}
}
for(int j = 0; j < 20; j++) {
for(int k = j-1; k >= 0; k--) {
if(rng[j] == rng[k]) similar[j][k] = 1;
}
}
while(q--) {
int m,x;
cin >> m >> x;
int ans = 0,taken;
bool done = 0; // indicates whether we performed the operation already
for(int k = 19; k >= 0; k--) {
//if current bit of x is 0
if(((1 << k) & x) == 0) {
if(rng[k].empty()) ans += (1 << k);
}
//if current bit of x is 1
else {
if(!done) {
if(rng[k].size() <= m) {
done = 1;
ans += (1 << k);
m -= rng[k].size();
taken = k;
}
}
else if(similar[taken][k]) ans += (1 << k);
}
}
cout << ans << '\n';
}
return;
}
int32_t main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);
int tc = 1;
cin >> tc;
for(int kase = 1; kase <= tc; kase++) {
//cout << "Case " << kase << ": ";
solve();
}
return 0;
}
Tester's code (C++)
// Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
// #define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
void solve()
{
int n,q;
cin >> n >> q;
assert(n >= 1);assert(n <= 2e5);
assert(q >= 1);assert(q <= 2e5);
vi a(n);
take(a,n);
for(auto x : a){
assert(x >= 0);assert(x <= 1e6);
}
int res = -1;
for(auto x : a)res &= x;
vi v[20];
rrep(i,19,0){
v[i].reserve(n);
rep(j,0,n){
if(a[j]&(1<<i))v[i].pb(1);
else v[i].pb(0);
}
}
vi con(20);
rep(i,0,20){
if(v[i][0] == 0)con[i]++;
rep(j,1,n){
if(v[i][j] == 0 && v[i][j-1] == 1)con[i]++;
}
}
vi gp(20,-1);
int z = 0;
rep(i,0,20){
if(gp[i] == -1){
gp[i] = z;
rep(j,0,20){
if(v[i] == v[j])gp[j] = z;
}
z++;
}
}
while(q--){
int k,x;
cin >> k >> x;
assert(1 <= k);assert(k <= n);
assert(x >= 0);assert(x <= 1e6);
vi bt;
rep(i,0,20){
if(x & (1<<i))bt.pb(i);
}
if(x == 0){
cout << res << "\n";
continue;
}
int top = -1;
rrep(i,bt.size()-1,0){
if((res & (1<<bt[i])))break;
if(con[bt[i]] <= k){
top = i;break;
}
}
if(top == -1){
cout << res << "\n";
continue;
}
int ans = res;
rrep(i,top,0){
if(gp[bt[i]] == gp[bt[top]]){
ans |= (1<<bt[i]);
}
else{
if(ans & (1<<bt[i]))ans ^= (1<<bt[i]);
}
}
cout << ans << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;cin >> t;
assert(t >= 1);
assert(t <= 3e5);
while(t--)
solve();
return 0;
}
Editorialist's code (Python)
import sys
input = sys.stdin.readline
for _ in range(int(input())):
n, q = map(int, input().split())
a = list(map(int, input().split()))
import random
hsh = [random.randint(0, 2**60 - 1) for i in range(n)]
changes, positions = [0]*20, [0]*20
for i in range(n):
for b in range(20):
if ~a[i] & 2**b:
positions[b] ^= hsh[i]
if i == 0 or (i > 0 and a[i-1] & 2**b):
changes[b] += 1
for i in range(q):
k, x = map(int, input().split())
ans = 0
chosen = -1
for b in reversed(range(20)):
if x & 2**b:
if changes[b] > k: continue
if chosen == -1 or chosen == positions[b]:
chosen = positions[b]
ans += 2**b
else:
ans += 2**b if changes[b] == 0 else 0
print(ans)