You are not logged in. Please login at www.codechef.com to post your questions!

×

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:

This question is marked "community wiki".

asked 13 Jun, 04:54

melfice's gravatar image

3★melfice
111
accept rate: 0%

edited 12 Jul, 00:23

admin's gravatar image

0★admin ♦♦
15.5k347484505

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×11,354
×1,812
×144
×3

question asked: 13 Jun, 04:54

question was seen: 270 times

last updated: 12 Jul, 00:23