Problem Statement: This problem appeared in February Cook-off Challenge on CodeChef.com. Below is the copy of problem statement from the website
Let X be the set of all integers between 0 and n-1. Suppose we have a collection S1, S2, …, Sm of subsets of X. Say an atom A is a subset of X such that for each Si we have either A is a subset of Si or A and Si do not have any common elements.
Your task is to find a collection A1, …, Ak of atoms such that every item in X is in some Ai and no two Ai, Aj with i ≠ j share a common item. Surely such a collection exists as we could create a single set {x} for each x in X. A more interesting question is to minimize k, the number of atoms.
Input
The first line contains a single positive integer t ≤ 30 indicating the number of test cases. Each test case begins with two integers n,m where n is the size of X and m is the number of sets Si. Then m lines follow where the i’th such line begins with an integer vi between 1 and n (inclusive) indicating the size of Si. Following this are vi distinct integers between 0 and n-1 that describe the contents of Si.
You are guaranteed that 1 ≤ n ≤ 100 and 1 ≤ m ≤ 30. Furthermore, each number between 0 and n-1 will appear in at least one set Si.
Output
For each test case you are to output a single integer indicating the minimum number of atoms that X can be partitioned into to satisfy the constraints.
Example
Input:
2
5 2
3 0 1 2
3 2 3 4
4 3
2 0 1
2 1 2
2 2 3
Output:
3
4
Solution:
Solution is to this problem can explained as follows.
We start by creating a Set/Atom A1 and choose a number x from the range 0….n-1 and create an Atom A1 such that A1 = {x}
Now Sx be is Set of all the sets Si such that x is a member of them . Sx = {0<=i <=m Si | x is an element of Si }
and S'x be the Set of all the sets Si such that x is not a member of them , S'x (0<=i<m Si | x is not an element of Si}
Now find all the numbers 0….n-1 such that each of them is in all the sets in Sx and is not in every set of S'x. Add all such numbers to A1. The Set A1 formed thus will be a subset of all the sets in Sx and will be disjoint of all the sets in S'x. Once we found A1, pick another number y from the remaining numbers from the range 0…n-1 and create Atom A2 = {y} and repeat the above process to complete the construction of A2. Repeat the creation of Atoms until all numbers from the range 0…n-1 have been exhausted. Number of Atoms formed is the answer.
Algorithm in above paragraph presents the concept without any optimization. Running time of above algorithm can be improved significantly using indexed bitmaps. The trick is to use a 30 bit bitmap for each number in range 0…n-1. thus bit at position j of bitmap[i] denote whether number i is in set Sj. This setting of bits can be easily done while reading the input for the sets Si. Once we have this array of bitmaps ready we, can sort them. Sorting bitmap array brings same bitmaps together. Now clusters of these same bitmaps represent the group of numbers from the range 0…n-1 such that they all belong to same Sj's and/or they all do not belong to Same Sj's. Counting these cluster gives us the answer.
Running time of this algorithm is m*p (reading sets and setting the bitmaps, where m is the number of sets Sj and p is the average number of elements in each set)+ nLog(n) ( sorting the bitmaps) + n (counting the clusters)