Connection Status:
Competition Arena > PlatypusPaternity

PlatypusPaternity

SRM 539 · 2011-11-22 · by vexorian

SRM 539 · 2011-11-22 · by vexorian · Simple Search, Iteration
Class Name: PlatypusPaternity
Return Type: int
Method Name: maxFamily
Arg Types: (vector<string>, vector<string>, vector<string>)
Problem Statement

Problem Statement

Our lab has just run into a dilemma. All our data about the lab's platypus population seems to have gotten mixed up. Each platypus in the lab is either a male adult, a female adult, or a child. The children are divided into several sibling groups. We know this division exactly. What we are missing are the parent-child relations. In order to reconstruct these, we conducted some genetic tests. We are going to do what some other lab did 4 years ago and hire you to make a program to help us fix the situation. You will be given three String[]s containing the results of these tests and the description of all sibling groups. The three String[]s are:

  • femaleCompatibility: The j-th character of the i-th element of femaleCompatibility is 'Y' if the i-th female adult is genetically compatible with the j-th child (i.e., the i-th female adult may be the mother of the j-th child). Otherwise, it is 'N'.
  • maleCompatibility: The j-th character of the i-th element of maleCompatibility is 'Y' if the i-th male adult is genetically compatible with the j-th child (i.e., the i-th male adult may be the father of the j-th child). Otherwise, it is 'N'.
  • siblingGroups: The j-th character of the i-th element of siblingGroups is 'Y' if the j-th child belongs to the i-th sibling group. Otherwise, it is 'N'. Each child belongs into exactly one sibling group. Two children are siblings if and only if they belong to the same sibling group.
The lab has defined a valid family as a set containing one female adult (mother), one male adult (father), and one sibling group. The mother and the father must be genetically compatible with each of the children in the sibling group. Return the maximum size of a family that follows these conditions or 0 if no such family exists.

Constraints

  • The input will represent data for F females, M males, C children and S sibling groups, with F, M, C and S each being between 1 and 50, inclusive.
  • femaleCompatibility will contain F elements.
  • maleCompatibility will contain M elements.
  • siblingGroups will contain S elements.
  • Each element of femaleCompatibility, maleCompatibility and siblingGroups will contain C characters.
  • Each character of femaleCompatibility, maleCompatibility and siblingGroups will be 'Y' or 'N' (quotes for clarity).
  • For each child j there will be exactly one sibling group i such that siblingGroups[i][j] is 'Y'.
  • For each sibling group i, there will exist at least one child that belongs to that group.
Examples
0)
{"YYYY", "YYYY"}
{"NNYN", "YYYN"}
{"YYYN", "NNNY"}
Returns: 5

One possible family is formed by the female adult 0 (0-indexed), the male adult 1, and the sibling group 0 (containing children 0, 1, and 2). The size of this family is: 1 female + 1 male + 3 children = 5 platypuses. There is no family of size more than 5. Another valid family of size 5 contains the female adult 1 instead of the female adult 0.

1)
{"NNYYY"}
{"YYNNN"}
{"YYNNN", "NNYYY"}
Returns: 0

Each adult is compatible with a different sibling group. There is no couple that is compatible with the same sibling group

2)
{"YYYYYYYYN"}
{"YYYYYYYYY"}
{"YNYNYNYNY",
 "NNNYNYNNN",
 "NYNNNNNYN"}
Returns: 4

The largest sibling group has size 5. However, there is no valid family that contains this sibling group, as the only available female adult is not compatible with one of the children in this group.

3)
{"YY"}
{"YY"}
{"YN", "NY"}
Returns: 3
4)
{"YYNNYYNNYYNN",
 "YNYNYNYNYNYN",
 "YYYNNNYYYNNN"}
{"NYYNNYYNNYYN",
 "YYNYYYNYYYNY",
 "NNNNNNYYYYYY"}
{"NYNNNYNNNNNN",
 "NNNNNNNNYNNN",
 "NNYNNNNNNNYN",
 "YNNNNNNYNNNN",
 "NNNNNNNNNYNY",
 "NNNYYNYNNNNN"}
Returns: 4

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

Coding Area

Language: C++17 · define a public class PlatypusPaternity with a public method int maxFamily(vector<string> femaleCompatibility, vector<string> maleCompatibility, vector<string> siblingGroups) · 124 test cases · 2 s / 256 MB per case

Submitting as anonymous