PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: munch_01
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Bitwise AND
PROBLEM:
You’re given an array A, which you can rearrange as you like.
After rearranging, define an array B where B_i = A_1\ \&\ A_2\ \&\ \ldots \ \&\ A_i. Find the lexicographically maximum value of B.
EXPLANATION:
When attempting to lexicographically maximize a sequence, by definition of the ordering it’s often helpful to be greedy - that is, maximize earlier indices without worrying about later indices at all.
B is the prefix AND array of A, so in particular B_1 = A_1 will hold.
So, to maximize B_1, clearly A_1 should be as large as possible: that is, the maximum element of A.
Next, B_2 = A_1\ \&\ A_2.
Since A_1 is fixed, it’s easy to maximize this in \mathcal{O}(N) time, of course: iterate across all remaining elements, and choose as A_2 whichever one among them maximizes B_2.
Then, similarly, we can maximize B_3 by greedily choosing A_3, then B_4 by greedily choosing A_4, and so on.
However, there are two issues that pop up with this approach:
- What do we do if, at some point, there are multiple choices of A_i that maximize B_i? We’ll need to decide which of them to take and which to leave for the future.
- The algorithm is clearly \mathcal{O}(N^2) because we make N choices each in linear time, which is too slow; so that needs to be improved.
The first issue is surprisingly easy to deal with: it doesn’t matter!
If there are multiple A_i that maximize B_i, any of them can be chosen - it won’t change future answers.
Why?
Since B_i = A_i\ \&\ B_{i-1}, the bits of A_i that aren’t set in B_{i-1} don’t matter at all (and won’t matter in the future, since taking bitwise AND doesn’t allow for unset bits to become set).
So, we can reduce every remaining element by taking its bitwise AND with B_{i-1} first, and the answer won’t change.
But then, since every remaining element is now a submask of B_{i-1}, the one that results in maximum bitwise AND is just the maximum remaining element! (there can be multiple copies of this maximum, and they could correspond to different initial elements before reduction with B_{i-1}, but nonetheless this shows that it doesn’t matter which of them is chosen to continue the sequence.)
As for speeding up the algorithm, observe that the prefix AND can change \leq\log\max A \leq 31 times (the only way it can change is by losing some bits that are set in it, and each bit can be lost at most once).
So, we can perform our algorithm in 31 ‘phases’.
In each phase, find all unchosen elements that result in the maximum prefix bitwise AND (as noted earlier, they’re equivalent), and then append them all to the answer while removing them from A. Of course, stop when A is empty.
This gives us a complexity of \mathcal{O}(N\log\max A), which is fast enough.
TIME COMPLEXITY:
\mathcal{O}(N\log\max A) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
vector <int> a(n);
for (auto &x : a) cin >> x;
int mx = 0;
for (auto x : a) mx = max(mx, x);
vector <int> c;
int curr = INT_MAX;
for (int i = 0; i < 32; i++){
vector <int> na;
int ok = -1;
for (auto x : a){
if ((curr & x) == curr){
c.push_back(x);
} else {
na.push_back(x);
ok = max(ok, x & curr);
}
}
a = na;
na.clear();
for (auto x : a){
if ((curr & x) == ok){
c.push_back(x);
curr = ok;
ok = -1;
} else {
na.push_back(x);
}
}
a = na;
}
for (auto x : a) c.push_back(x);
curr = INT_MAX;
for (auto x : c){
curr &= x;
cout << curr << " ";
}
cout << "\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>
using namespace std;
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
input_checker inp;
int T = inp.readInt(1, (int)2e4); inp.readEoln();
int NN = 0;
while(T-- > 0) {
int N = inp.readInt(1, (int)2e5); inp.readEoln(); NN += N;
vector<int> A = inp.readInts(N, 1, (int)1e9); inp.readEoln();
vector<int> val(N);
sort(A.rbegin(), A.rend());
int nd = A.front(), p = 0;
while(nd > 0) {
for(int j = 0 ; j < N ; ++j) if((A[j] & nd) == nd) {
val[p++] = nd;
A[j] = 0;
}
int f = 0;
for(int j = 0 ; j < N ; ++j) f = max(f, nd & A[j]);
nd = f;
}
for(int i = 0 ; i < N ; ++i) cout << val[i] << " \n"[i == N - 1];
}
assert(NN <= (int)2e5);
inp.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
mark = [0]*n
x = (2**31) - 1
ans = []
while len(ans) < n:
mx = 0
for i in range(n):
if mark[i]: continue
mx = max(mx, x & a[i])
for i in range(n):
if mark[i]: continue
if (x & a[i]) == mx:
mark[i] = 1
ans.append(x & a[i])
x = ans[-1]
print(*ans)