PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
DFS/BFS
PROBLEM:
You’re given two arrays A and B. You can swap A_i with B_i for an index i, as many times as you like.
Maximize the sum of the bitwise ANDs of the arrays A and B.
EXPLANATION:
Essentially, we have N pairs of (A_i, B_i), and we need to decide their orientation.
Given that we’re looking at bitwise operations, it makes sense to look at bits one by one, from highest to lowest.
So, suppose we’re currently looking at bit k.
Then,
- If all 2N values A_i and B_i have k set, then k will definitely be set in the bitwise AND of both arrays no matter what we do.
So, we can just add 2\cdot 2^k to the answer, and forget about this bit entirely. - In a similar vein, if for some i both A_i and B_i don’t have this bit set, both arrays can never have it set in their bitwise ANDs, so we ignore such bits.
- This leaves us with a bit that can be set in either A or B, but not both.
Such bits are the interesting ones, and we need to figure out what to do with them.
Let’s now ignore the fixed bits, and work with only interesting ones.
Let b_1 be the highest interesting bit.
Note that it can be set in either A or B (or neither), but not both - that’s why it’s interesting.
It’s also clearly not optimal to have it unset in both A and B, because we’re working with distinct powers of two: if we set this it will always give a larger profit than not setting it and working with only lower bits.
So, our choice is now whether it should be set in A or in B.
Since it’s an interesting bit, each (A_i, B_i) pair must be either (0, 1), (1, 0), or (1, 1) with respect to having this bit set or not.
If it’s (1, 1) then the orientation of this pair doesn’t matter (yet) so we ignore it.
For the (1, 0) and (0, 1) pairs though, depending on whether we choose A or B, their orientation becomes fixed - either all of them have to become (1, 0) or all of them have to become (0, 1).
Now, it’s not always immediately possible to choose whether the bit should be set in A or in B without further information.
However, observe that the relative orientation of such pairs is fixed, no matter whether we choose to have the bit in A or B.
This is a useful tool.
For each index, there are two possible states: either it’s flipped, or it’s not.
Now, suppose we go through interesting bits in order from high to low.
For the bit we’re currently processing, only those indices i such that A_i and B_i are not equal at this bit matter, as noted above.
Let these indices be i_1, i_2, \ldots, i_k.
Now, the relative orientation of these indices is fixed: all indices of the form (1, 0) in this bit must be in the same orientation, all indices of the form (0, 1) must be in the same orientation, and these two orientations must be opposite.
Let’s create a graph with 2N vertices, where each i (1 \leq i \leq N) has two vertices corresponding to it: (i, 0) meaning index i isn’t flipped, and (i, 1) meaning index i is flipped.
Going back to the relative orientations: suppose we add an edge between the orientations of i_1 and i_2 that need to be the same, then those of i_2 and i_3 that need to be the same, and so on.
Essentially, all vertices in the same connected component have their orientations fixed if one vertex’s orientation is fixed.
This will break exactly when (i, 0) and (i, 1) both lie in the same component for some i, and will otherwise always be valid.
Now, note that we added only \mathcal{O}(N) edges, and checking whether (i, 0) and (i, 1) are connected for some i can also be done easily enough in linear time (in the size of the graph).
This gives us a pretty straightforward solution.
Iterate through interesting bits in descending order, while maintaining the graph so far.
For each such bit:
- Add the \mathcal{O}(N) edges as described above, between the vertices i_1, i_2, \ldots, i_k that will end up being fixed.
- In the resulting graph, check if some (i, 0) and (i, 1) lie in the same component.
- If yes, this bit can’t be set in either A or B without breaking some higher bit, which is not worth it.
So, delete all the newly added edges and carry on. - If there are no conflicts, add 2^b to the answer and keep the edges in the graph.
There are \mathcal{O}(\log \max A) bits to process, and for each of them we add \mathcal{O}(N) edges, so there are a total of \mathcal{O}(N\log\max A) edges added at all.
We perform a DFS/BFS on this graph \mathcal{O}(\log\max A) times (once for each bit), making the overall complexity \mathcal{O}(N\log^2 \max A).
TIME COMPLEXITY:
\mathcal{O}(N\log^2 \max A) 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());
struct ufds{
vector <int> root, sz;
int n;
void init(int nn){
n = nn;
root.resize(n + 1);
sz.resize(n + 1, 1);
for (int i = 1; i <= n; i++) root[i] = i;
}
int find(int x){
if (root[x] == x) return x;
return root[x] = find(root[x]);
}
bool unite(int x, int y){
x = find(x); y = find(y);
if (x == y) return false;
if (sz[y] > sz[x]) swap(x, y);
sz[x] += sz[y];
root[y] = x;
return true;
}
};
void Solve()
{
int n; cin >> n;
vector <int> a(n), b(n);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
// get restrictions between bits
int l = 30;
vector<vector<int>> req(l, vector<int>(l, 0));
vector <int> can(l, 1);
int all = (1 << l) - 1;
for (int i = 0; i < n; i++){
all &= a[i];
all &= b[i];
for (int bit = 0; bit < l; bit++){
int aa = a[i] >> bit & 1;
int bb = b[i] >> bit & 1;
if (aa == 0 && bb == 0){
can[bit] = 0;
continue;
}
if (aa == bb){
continue;
}
for (int s = 0; s < bit; s++) if (can[s]){
int cc = a[i] >> s & 1;
int dd = b[i] >> s & 1;
if (cc == dd){
continue;
}
if (aa == cc){
req[s][bit] |= 1;
} else {
req[s][bit] |= 2;
}
}
}
}
int ans = 0;
vector <bool> take(l, false);
ufds uf;
uf.init(2 * l);
for (int i = l - 1; i >= 0; i--){
if (!can[i]) continue;
if (all >> i & 1) continue;
ufds uf2 = uf;
for (int j = i + 1; j < l; j++){
if (take[j]){
if (req[i][j] & 1){
uf2.unite(i, j);
uf2.unite(i + l, j + l);
}
if (req[i][j] & 2){
uf2.unite(i, j + l);
uf2.unite(i + l, j);
}
}
}
bool good = true;
for (int j = 0; j < l; j++){
good &= uf2.find(j) != uf2.find(j + l);
}
if (good){
ans += 1 << i;
take[i] = true;
uf = uf2;
}
}
ans += all * 2;
cout << ans << "\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;
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 4e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
vector<pll> adj[N];
vector<ll> col(N,-1);
bool is_good;
void dfs1(ll u){
for(auto [v,w] : adj[u]){
ll want = col[u]^w;
if(col[v] == -1){
col[v] = want;
dfs1(v);
}
else{
if(col[v] != want){
is_good = false;
}
}
}
}
void solve(int test_case){
ll n; cin >> n;
vector<ll> a(n+5), b(n+5);
rep1(i,n) cin >> a[i];
rep1(i,n) cin >> b[i];
rep1(i,2*n){
adj[i].clear();
}
auto add_edge = [&](ll u, ll v, ll w){
adj[u].pb({v,w}), adj[v].pb({u,w});
};
rep1(i,n){
add_edge(i,i+n,1);
}
ll ans = 0;
rev(bit,29,0){
bool zz = false;
vector<array<ll,3>> edges;
ll prev_guy = -1;
rep1(i,n){
ll x = a[i], y = b[i];
ll b1 = 0, b2 = 0;
if(x&(1<<bit)) b1 = 1;
if(y&(1<<bit)) b2 = 1;
if(b1 and b2) conts;
if(!b1 and !b2){
zz = true;
conts;
}
if(prev_guy != -1){
ll curr_guy = i;
if(!b1) curr_guy = i+n;
edges.pb({prev_guy,curr_guy,0});
}
if(b1) prev_guy = i;
else prev_guy = i+n;
}
if(zz) conts;
if(prev_guy == -1){
ans += 1<<(bit+1);
conts;
}
for(auto [u,v,t] : edges){
add_edge(u,v,t);
}
rep1(i,2*n) col[i] = -1;
is_good = true;
rep1(i,2*n){
if(col[i] != -1) conts;
col[i] = 0;
dfs1(i);
}
if(is_good){
ans += 1<<bit;
}
else{
for(auto [u,v,t] : edges){
adj[u].pop_back();
adj[v].pop_back();
}
}
}
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}