PROBLEM LINK:Author: Praveen Dhinwa DIFFICULTY:MEDIUM PREREQUISITES:None PROBLEM:You are given $N$ integer sets containing numbers from $1$ to $K$. You are to calculate the number of pairs of sets such that their union contains all the $K$ distinct numbers. EXPLANATION:Since the total amount of elements in the sets is not greater than $10^4$, there are at most $ \dfrac{2\cdot10^4}{k}$ sets which have at least $\dfrac k 2$ elements. Each pair has to have at least one element from this set so we can bruteforce such pairs and check if they're ok using bitsets in at most $n\times \dfrac{2\cdot 10^4}{k}\times \dfrac{k}{32}=625n$ operations. The other solution is to iterate over all pairs of the sets, $s_i, s_j$. If $s_i + s_j < k$, then their union obviously can't have $k$ elements. Otherwise, for this pair we can found the union in $\mathcal{O}(s_i + s_j)$ time. You can prove that this approach will work in time. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution will be updated soon. RELATED PROBLEMS:
This question is marked "community wiki".
asked 13 Jun, 04:54
