codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1882B.md (2269B)


      1 Source: https://codeforces.com/problemset/problem/1882/B
      2 
      3 B. Sets and Union
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 Find the maximum number of elements in an attainable $S$ such that $S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}$.
     24 
     25 $^{\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\}$.
     26 
     27 Input
     28 
     29 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.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \le n \le 50$).
     32 
     33 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} \lt s_{i, 2} \lt \ldots \lt s_{i, k_{i}} \le 50$) — the elements of $S_{i}$.
     34 
     35 Output
     36 
     37 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}$.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4
     45 
     46 3
     47 
     48 3 1 2 3
     49 
     50 2 4 5
     51 
     52 2 3 4
     53 
     54 4
     55 
     56 4 1 2 3 4
     57 
     58 3 2 5 6
     59 
     60 3 3 5 6
     61 
     62 3 4 5 6
     63 
     64 5
     65 
     66 1 1
     67 
     68 3 3 6 10
     69 
     70 1 9
     71 
     72 2 1 3
     73 
     74 3 5 8 9
     75 
     76 1
     77 
     78 2 4 28
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 4
     85 5
     86 6
     87 0
     88 ```
     89 
     90 Note
     91 
     92 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\}$.
     93 
     94 In the second test case, we can pick $S = S_{2} \cup S_{3} \cup S_{4} = \{2, 3, 4, 5, 6\}$.
     95 
     96 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\}$.
     97 
     98 In the fourth test case, the only attainable set is $S = \varnothing$.