×

# UNIONSET - Editorial

Author: Praveen Dhinwa
Tester: Prateek Gupta
Editorialist: Oleksandr Kulkov

MEDIUM

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:

This question is marked "community wiki".

2★melfice
51213
accept rate: 0%

17.6k347489517

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×12,790
×2,044
×148
×3

question asked: 13 Jun '17, 04:54

question was seen: 506 times

last updated: 12 Jul '17, 00:23