PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Prateek Gupta
Editorialist: Oleksandr Kulkov
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.
Tester’s solution will be updated soon.
Editorialist’s solution can be found here.