GOODSUBSET - 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:

Combinatorics, prefix sums

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 N, compute the sum of f(S) across all non-empty subsets of [1, 2, \ldots, N].

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.

This observation can now be used to solve the problem.

Let’s split the elements [1, N] into several buckets, based on their msb’s.
Each bucket will be a contiguous interval, and the buckets will look like [1], [2, 3], [4, 7], [8, 15], \ldots

Suppose we have r buckets, and let s_i denote the size of the i-th bucket.
Note that r is about \log_2 N.

For any subset S, observe that f(S) will equal the largest number of elements of S that are present among any one bucket - that is, the maximum size of S intersected with some bucket.

With this in mind, let’s fix a value K (1 \le K \le N) and try to count the number of subsets S for which f(S) = K.
If we’re able to do this, we can multiply this count by K and add it to the answer.

For the answer of a subset to be K,

  • There must be at least one bucket from which K elements are chosen, and
  • At most K elements can be chosen from every bucket.

This can be counted as: start with all subsets that include at most K elements from every bucket; and from this subtract all subsets that have at most K-1 elements from every bucket.

How many buckets include at most K elements from each bucket?
Well, if we look at the i-th bucket,

  • If s_i \le K, we can take any number of elements from this bucket.
    Thus, there are 2^{s_i} options.
  • If s_i \gt K, then there are \binom{s_i}{x} ways to choose x elements from the bucket, and thus the total number of ways equals
    \sum_{x=0}^{K} \binom{s_i}{x}

This is just a prefix sum of the \binom{s_i}{x} values, and we can hence precompute and store this value for every bucket.
Note that \sum s_i = N, and hence computing and storing all these prefix sums takes only linear time and memory.

The total number of ways is then obtained by multiplying the number of ways for each bucket.
This gives us the number of subsets with \le K elements from each bucket; do the same thing for \le K-1 elements and subtract this from the initial value to get the requisite count.

Since there are around \log_2 N buckets, a fixed value of K can be processed in \mathcal{O}(\log N) time.
Thus, we have a solution that’s \mathcal{O}(N\log N), which is fast enough for us.

It’s possible to optimize the solution to \mathcal{O}(N), utilizing the fact that we don’t need to iterate over all buckets for each K and rather only need to consider buckets with size not less than K.
The i-th bucket will thus only be considered for K \le s_i, and so the overall work done across all K equals \mathcal{O}(s_1 + s_2 + \ldots + s_r) = \mathcal{O}(N).
However, this was not needed to get AC.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
mod = 998244353
fac = [1] + list(range(1, 200005))
for i in range(1, 200005): fac[i] = (i * fac[i-1]) % mod
def C(n, r):
    if r < 0 or r > n: return 0
    return fac[n] * pow(fac[r] * fac[n-r], mod-2, mod) % mod

for _ in range(int(input())):
    n = int(input())

    sizes = []
    for k in range(20):
        lo, hi = 2**k, 2**(k+1) - 1
        if lo > n: break
        hi = min(hi, n)
        sizes.append(hi - lo + 1)

    pref = []
    for s in sizes:
        pref.append([])
        cur = 0
        for i in range(s+1):
            cur = (cur + C(s, i)) % mod
            pref[-1].append(cur)

    f = [1]*(n+1)
    for k in range(1, n+1):
        for p in pref:
            if len(p) <= k: f[k] *= p[-1]
            else: f[k] *= p[k]
            f[k] %= mod

    ans = 0
    for k in range(1, n+1):
        ans += k*(f[k] - f[k-1])
    print(ans % mod)