PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wesam13
Tester: satyam_343
Editorialist: iceknight1093
DIFFICULTY:
1688
PREREQUISITES:
Observation
PROBLEM:
You’re given an array A of length N.
It’s known that 2\cdot (A_1 \oplus A_2 \oplus \ldots \oplus A_N) \geq (A_1 \mid A_2 \mid \ldots \mid A_N).
Do the following N times:
- Choose an element x remaining in the array.
- Either create a new box and add x to it, or add x to an existing box whose XOR is at least x.
Find the minimum number of boxes needed.
EXPLANATION:
Let’s make some observations.
Let B be the maximum bit present in some array element.
Let’s call some A_i good if it contains B.
Then, note that:
- No box can contain \geq 3 good elements.
- If a non-empty box contains only non-good elements, we can never insert a good element into it.
- If a box contains exactly one good element, we can insert as many non-good elements into it as we like.
Proof
All three claims are fairly easy to prove once you’ve written them down.
- When the second good element is inserted into a box, the xor of this box no longer contains bit B; which means it only contains bits strictly smaller than B.
This means any good element is strictly larger than this XOR, and can no longer be inserted into it. - The second claim also follows from similar logic: with only non-good elements, any good element is strictly larger than their XOR since only bits less than B are used.
- The third claim is similar: with exactly one good element, the XOR will contain B.
This makes it strictly larger than any non-good element, so any such element can always be inserted.
So, suppose there are k good elements in the array.
Then, notice that we surely need at least \left \lceil \frac{k}{2} \right\rceil boxes; since each box can contain at most 2 good elements.
If k were odd, using exactly \left \lceil \frac{k}{2} \right\rceil boxes is possible, as follows:
- Keep one good element aside, and pair the rest.
- Put the unpaired element into one box, and then all the non-good elements.
- Then, for each pair of good elements, put the larger one into a new box, then the smaller one.
Now, recall the condition 2\cdot (A_1 \oplus A_2 \oplus \ldots \oplus A_N) \geq (A_1 \mid A_2 \mid \ldots \mid A_N).
This really just means that B, the largest bit, is present in the XOR of all elements.
This is only possible when B occurs an odd number of times, i.e, the number of good elements is odd.
We’ve already solved the odd case, so we’re done!
TIME COMPLEXITY
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int& p : a) cin >> p;
const auto get_max = [&](int num) -> int {
for (int bit = 60; bit >= 0; bit--) {
if ((1ll << bit) & num) return bit;
}
assert(false);
return -1;
};
int mx = 0;
for (const int& p : a)
mx = max(mx, get_max(p));
int cnt = 0;
for (const int& p : a)
if ((p & (1ll << mx)))
++cnt;
cout << ((cnt + 1) >> 1) << '\n';
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
x = max(a)
mxbit = 60
while x & (2 ** mxbit) == 0: mxbit -= 1
ct = 0
for i in range(n):
ct += a[i] >> mxbit
print((ct + 1)//2)