GOODSUBSETEZ - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

A set S is called good if for every x, y \in S such that x \lt y, the condition x\oplus y \lt x\& y holds.

Define f(S) to be the size of the largest good subset of S.
Given S, compute f(S).

EXPLANATION:

We begin by analyzing what it means for a set to be good.
More importantly, we need to understand when x\oplus y \lt x\& y can hold.

Note that x\oplus y has exactly those bits set which are set in one of x and y but not the other.
On the other hand, x\& y has those bits set which are set in both x and y.
In particular, x\oplus y and x\& y do not share any set bits at all.

Thus, which one among them is larger, is determined purely by whichever one has the larger maximum set bit.
That is, if we define msb(x) to be the maximum set bit in x, then x\oplus y \lt x\& y if and only if msb(x\oplus y) \lt msb(x\& y).

These two msb’s can now be related to msb(x) and msb(y).
In particular,

  • If msb(x) = msb(y), then msb(x\oplus y) \lt msb(y) but msb(x\& y) = msb(y) because the same highest bit is set in x and y.
  • On the other hand, is msb(x) \ne msb(y), then msb(x\oplus y) = msb(y) and msb(x\& y) \lt msb(y), since the two values differ at msb(y).
    (Note that this is under the assumption of x \lt y, so that msb(x) \le msb(y)).

Thus, we get a rather simple criterion: x\oplus y \lt x\& y if and only if x and y have the same msb.

This analysis applies to any pair (x, y), and so extending it to all pairs of a set S, we see that S is good if and only if every element of S has the same msb.

We can use this observation to compute the size of the largest good subset of the given array S.

First, record the msb of each element of S.
Since S_i \le 10^9, we have msb(S_i) \le 30 so only about 30 bits need to be checked.

After this, the answer is simply the largest frequency among these msb’s.
This is easy to find, for example with a frequency array.

TIME COMPLEXITY:

\mathcal{O}(N\log \max(S)) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = list(map(int, input().split()))
    
    freq = [0]*35
    for x in s:
        for b in reversed(range(35)):
            if x & (1 << b):
                freq[b] += 1
                break
    print(max(freq))