TopCoder problem "BorelSets" used in TCCC '04 Qual. 4 (Division I Level Two)



Problem Statement

    *** You may only submit a given problem once - no resubmissions will be accepted. ***



Suppose there is a universal set called U containing the integers between 1 and size inclusive. You will be given some subsets of U. A subset of U is a set of numbers that are in U. The set can contain no numbers (empty set), every number in U, or anything in between. Each subset will be given as a String containing a single space-delimited list of the numbers in the set. The Borel Field B (also called sigma-algebra) generated by subsets is the smallest collection of sets satisfying the following statements:
  • 1) All of the sets in subsets are in B,
  • 2) if X and Y are sets in B then X union Y is in B,
  • 3) if X is a set in B then the complement of X is in B.
Given two sets of numbers, the union is the set of all numbers that are in either or both. The complement of a set X contains all numbers that are in U but not in X (if U=X the complement of X is empty). Given subsets you will return how many distinct sets are in the Borel Field it generates. When comparing sets to see if they are distinct, note that duplicate elements within a set are ignored. In other words, a set does not have any duplicates, but a description of the set may. For example, the sets "1 1 2", "1 2", and "2 2 1" are indistinguishable as sets, but "1 2 3" is distinct from the previous three.
 

Definition

    
Class:BorelSets
Method:howMany
Parameters:int, String[]
Returns:int
Method signature:int howMany(int size, String[] subsets)
(be sure your method is public)
    
 

Constraints

-size will be between 1 and 10 inclusive.
-subsets will contain between 1 and 50 elements inclusive.
-Each element of subsets will contain between 0 and 50 characters inclusive.
-Each element of subsets will either be an empty string, or a single space-delimited list of integers. Each integer in the list will be between 1 and size inclusive, and will have no leading zeros.
-Each element of subsets will not have any leading or trailing spaces.
 

Examples

0)
    
4
{"1 2",""}
Returns: 4
We have that 
   U = "1 2 3 4".
We know "1 2", and "" are in the resultant Borel Field. By taking the complement of "1 2" we get "3 4". By taking the complement of "" we get "1 2 3 4". There are no other sets in the Borel Field.
1)
    
10
{"","1","2","3","4","5","6","7","8","9","10"}
Returns: 1024
2)
    
5
{"","1 1 2","1 1 2 2 1 1","","2 1 1"}
Returns: 4

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2322

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5003&pm=2322

Writer:

brett1479

Testers:

lbackstrom , schveiguy

Problem categories:

Math, Search