TopCoder problem "MarriageProblemRevised" used in SRM 356 (Division I Level Two)



Problem Statement

    There are several unmarried men and women living in a society where marriage is defined as either one husband with one or more wives, or one wife with one or more husbands. You are given a String[] preferences. The j-th character of the i-th element of preferences is '1' (one) if the i-th man and the j-th woman are willing to be part of the same marriage, and '0' (zero) otherwise.

Your task is to group these people into the minimum possible number of marriages. Each person must be a member of exactly one marriage, and each marriage must contain only willing members. Return the number of marriages, or -1 if this is not possible.
 

Definition

    
Class:MarriageProblemRevised
Method:neededMarriages
Parameters:String[]
Returns:int
Method signature:int neededMarriages(String[] preferences)
(be sure your method is public)
    
 

Constraints

-preferences will contain between 1 and 12 elements, inclusive.
-The length of each element of preferences will be betwen 1 and 12, inclusive.
-All elements of preferences will be of the same length.
-Each element of preferences will contain only '0' (zeroes) and '1' (ones).
 

Examples

0)
    
{"111"}
Returns: 1
Here, we have one man and three women, and everybody is willing to be in the same marriage. Therefore, we only need one marriage.
1)
    
{"100", "010", "001"}
Returns: 3
2)
    
{"00", "00"}
Returns: -1
Nobody is willing to be in the same marriage as anybody else, so there cannot be any marriages in this case.
3)
    
{"0001", "0001", "0001", "1111"}
Returns: 2
4)
    
{"11101011","00011110","11100100","01010000","01000010","10100011","01110110","10111111"}
Returns: 3

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10765&pm=6608

Writer:

Pawa

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Graph Theory, Math