SUMREDUCTION - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There’s an array A.
You can repeat the following operation:

  • Choose elements A_i and A_j such that A_i \ \&\ A_j = 0
    Delete these two elements from A and insert A_i + A_j into A.

Is it possible to end up with A containing only a single element?

EXPLANATION:

Our operation takes two elements A_i and A_j that don’t share any set bits, deletes them, and then inserts A_i + A_j into the array.
Note that if A_i and A_j don’t share any set bits, then the set bits of A_i + A_j are exactly all bits set in either A_i or A_j.

This means that performing an operation doesn’t lose any bits set in the array.

Our objective is to end up with only a single element.
This single element, obviously, can contain any bit at most once.

However, since our operation doesn’t lose any bits, this means the initial array must also contain every bit at most once!
If some bit appears two (or more times), we’ll never be able to merge together two occurrences of elements containing this bit.

Thus, a necessary condition for the answer to be Yes is that every bit appears in at most one element of A.
It’s easy to see that this condition is also sufficient: if every bit appears at most once, it means that no pair of elements share any bits at all, i.e. the bitwise AND of any pair of elements is 0.
This means we can simply repeatedly merge any pair of elements and we’ll end up with a single element in the end.

So, all that needs to be done is to check whether each bit appears at most once in the array.
This can be done in \mathcal{O}(30\cdot N) time by running a check for each bit from 0 to 30, or in \mathcal{O}(N^2) time by checking if (A_i \ \&\ A_j) = 0 for all pairs (i, j).
The constraints are low so either approach is fast enough.

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    ans = 'Yes'
    for i in range(n):
        for j in range(i+1, n):
            if (a[i] & a[j]) > 0:
                ans = 'No'
    print(ans)
2 Likes