Connection Status:
Competition Arena > MarriageProblemRevised

MarriageProblemRevised

SRM 356 · 2007-07-02 · by Pawa

SRM 356 · 2007-07-02 · by Pawa · Graph Theory, Math
Class Name: MarriageProblemRevised
Return Type: int
Method Name: neededMarriages
Arg Types: (vector<string>)
Problem Statement

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.

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

Submissions are judged against all 96 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MarriageProblemRevised with a public method int neededMarriages(vector<string> preferences) · 96 test cases · 2 s / 256 MB per case

Submitting as anonymous