UNIONSET - Editorial

PROBLEM LINK:

Practice
Contest

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.

RELATED PROBLEMS: