# BOX95 - Editorial

Author: wesam13
Tester: satyam_343
Editorialist: iceknight1093

1688

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)

4 Likes

What was the need for the statement 2⋅(A1⊕A2⊕…⊕AN) ≥ (A1∣A2∣…∣AN) ? Shouldn’t the answer either way be (cnt+1)/2 ?

As you can see in the editorial, that condition guarantees that the number of elements with largest bit is odd.

If that count is even, it’s not so simple.
For example, if A = [3, 3, 1] then there are 2 elements with highest bit set, but it’s not actually possible to put them all in one box.
On the other hand, A = [3, 3] has the same count, but this time you can put them in one box - so it’s impossible to decide the number of boxes just by looking at count in the even case.

Thenks!

What if number of elements with MSB set are 0 ??In that case, what would be the answer

1

because MSB 0 means all elements are 0 , which can be placed in 1 box

but that goes against constraint of problem