1276. Two Groups That Cover Everything Between Them
k groups over n items are given, each as a mask. Decide whether some two of
them, possibly the same group twice, cover every item between them. Print YES
or NO.
n=3 groups 5 2 -> YES 101 | 010 = 111
n=3 groups 5 1 -> NO 101 | 001 = 101
n=2 groups 3 -> YES the single group already covers both, paired with itself
n=3 groups 1 2 4 -> NO no PAIR reaches 111, though all three together do
## What most people try first
All pairs. That is O(k^2) ORs, which at k = 200000 is 2 * 10^10. It is
correct, and the fix is not a better pair loop; it is to stop looking for the
partner and start asking whether an adequate partner EXISTS.
## What an adequate partner is
Fix a group A. A partner B works exactly when A | B is the full set, which
means B must contain every item A is missing:
B works if and only if B contains (full XOR A)
B may contain more than that; the requirement is only that it misses nothing
A misses. So for each A the question is: among the given masks, is any one a
SUPERSET of a particular target mask?
## The direction that catches people out
That is a superset question, not a submask question. Getting it backwards is
the mistake this problem is built around, because the two indexes have almost
identical code and both produce plausible answers. Precomputing "is some given
mask a SUBMASK of x" and querying it at x = full XOR A answers a different
question entirely, and on n=3 with groups 1 2 4 it reports YES where the
answer is NO: every given mask is a submask of every complement here, and none
is a superset of one.
## Precompute the index once
Mark present[m] for each given mask, then run #1273's superset transform with
OR in place of addition:
has[m] = present[m]
for b in 0 .. n-1:
for m in 0 .. 2^n - 1:
if m does NOT have bit b: has[m] = has[m] or has[m | (1 << b)]
After this, has[m] is true exactly when some given mask contains m. The
argument is #1273's with max replaced by or, both of which are idempotent
and associative, which is why the same layering works and why no
double-counting question arises: OR does not care how many times a true value
arrives.
Then the answer is
YES if has[full XOR A] for some given group A
## Why pairing a group with itself must be allowed
n=2 with the single group 3: it already covers everything, so the answer is
YES with A = B. A solution that insists on two DISTINCT indices answers NO.
The statement allows the same group twice for this reason, and the check falls
out automatically, since present[A] is true and A contains
full XOR A whenever A is full.
## Cost
O(2^n * n + k): about 20971520 steps at n = 20, plus one lookup per group,
against O(k^2)'s 2 * 10^10. Note the cost no longer depends on k except
linearly, which is the real win when k is much larger than 2^n.
## Width
n is at most 20, so masks are at most 1048575 and the array has at most
1048576 entries. Every mask fits in a signed 32-bit integer, limit
2147483647, and JavaScript's |, & and ^ are safe on plain Numbers
because every value already fits in signed 32 bits. The stored values are
booleans, so nothing accumulates and no overflow is possible at any width.
Constraints - `1 ≤ n ≤ 20` - `1 ≤ k ≤ 200000` - `0 ≤ each mask ≤ 2^n - 1`
Input
The first line contains two integers n and k, separated by a space.
The second line contains k integers: the group masks.
Output
Print YES if some two of the given groups, possibly the same one twice, together cover all n items, and NO otherwise. Print nothing else.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.