Sets and Union (Codeforces 1882B)
Tags: Greedy, bitmasks

You have $$$n$$$ sets of integers $$$S_{1}, S_{2}, \ldots, S_{n}$$$. We call a set $$$S$$$ attainable, if it is possible to choose some (possibly, none) of the sets $$$S_{1}, S_{2}, \ldots, S_{n}$$$ so that $$$S$$$ is equal to their union$$$^{\dagger}$$$. If you choose none of $$$S_{1}, S_{2}, \ldots, S_{n}$$$, their union is an empty set.Find the maximum number of elements in an attainable $$$S$$$ such that $$$S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}$$$.$$$^{\dagger}$$$ The union of sets $$$A_1, A_2, \ldots, A_k$$$ is defined as the set of elements present in at least one of these sets. It is denoted by $$$A_1 \cup A_2 \cup \ldots \cup A_k$$$. For example, $$$\{2, 4, 6\} \cup \{2, 3\} \cup \{3, 6, 7\} = \{2, 3, 4, 6, 7\}$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 50$$$).The following $$$n$$$ lines describe the sets $$$S_1, S_2, \ldots, S_n$$$. The $$$i$$$-th of these lines contains an integer $$$k_{i}$$$ ($$$1 \le k_{i} \le 50$$$) — the number of elements in $$$S_{i}$$$, followed by $$$k_{i}$$$ integers $$$s_{i, 1}, s_{i, 2}, \ldots, s_{i, k_{i}}$$$ ($$$1 \le s_{i, 1} < s_{i, 2} < \ldots < s_{i, k_{i}} \le 50$$$) — the elements of $$$S_{i}$$$.

Output: For each test case, print a single integer — the maximum number of elements in an attainable $$$S$$$ such that $$$S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}$$$.

Note: In the first test case, $$$S = S_{1} \cup S_{3} = \{1, 2, 3, 4\}$$$ is the largest attainable set not equal to $$$S_1 \cup S_2 \cup S_3 = \{1, 2, 3, 4, 5\}$$$.In the second test case, we can pick $$$S = S_{2} \cup S_{3} \cup S_{4} = \{2, 3, 4, 5, 6\}$$$.In the third test case, we can pick $$$S = S_{2} \cup S_{5} = S_{2} \cup S_{3} \cup S_{5} = \{3, 5, 6, 8, 9, 10\}$$$.In the fourth test case, the only attainable set is $$$S = \varnothing$$$.

Sample Inputs:
4
3
3 1 2 3
2 4 5
2 3 4
4
4 1 2 3 4
3 2 5 6
3 3 5 6
3 4 5 6
5
1 1
3 3 6 10
1 9
2 1 3
3 5 8 9
1
2 4 28

Sample Outputs:
4
5
6
0

Solution (Python):
n = int(input())
for _ in range(n):
    nn = int(input())
    k = [0] * nn
    s = [0 for __ in range(nn)]
    sall = set()
    for i in range(nn):
        k_l = list(map(int, input().split()))
        k[i] = k_l[0]
        s[i] = set(k_l[1:])
        sall = sall.union(s[i])
    lenall = len(sall)
    ans = 0
    fp = 0
    for x in sall:
        temps = set()
        for xs in s:
            if x not in xs:
                temps = temps.union(xs)
        lentemp = len(temps)
        if lentemp == lenall - 1:
            print(lenall - 1)
            fp = 1
            break
        ans = max(ans, lentemp)
    if fp == 0:
        print(ans)

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    S = []
    for _ in range(n):
        S.append(set(map(int, input().split()[1:])))
    Union = set().union(*S)
    max_number = 0
    for i in Union:
        max_number = max(max_number, len(set().union(*[s for s in S if i not in s])))
    print(max_number)

Solution (Python):
def solve():
    numSet = int(input())
    sets = []
    for _ in range(numSet):
        arr = list(map(int, input().split()[1:]))
        num = 0
        for x in arr:
            num |= 1 << x - 1
        sets.append(num)
    allElement = 0
    for x in sets:
        allElement |= x
    maxUnionSize = 0
    for x in range(51):
        if not 1 << x & allElement:
            continue
        theUnion = 0
        for aSet in sets:
            if aSet & 1 << x:
                continue
            theUnion |= aSet
        maxUnionSize = max(maxUnionSize, bin(theUnion).count('1'))
    print(maxUnionSize)
for _ in range(int(input())):
    solve()