FamilyTree
TCO06 Round 3 · 2006-03-01 · by Olexiy
TCO06 Round 3 · 2006-03-01 · by Olexiy · Graph Theory
Problem Statement
Problem Statement
We are keeping a family tree. We update the data by adding information as it
becomes available. When information arrives that is not
consistent with the previous data, we need to recognize that fact immediately.
We will enforce only the most obvious rules:
- A person is either male or female.
- A child's parent cannot be the child itself or a descendant of the child
- A child has two parents, one male and the other female.
Each piece of data gives either the names of a child and parent or the name of
a person and that person's gender. All occurrences of a name represent the same person.
Create a class FamilyTree that contains a method firstBad that is given a
Each element of data will be formatted in one of these two forms:
"childname parentname"
"name gender"
where the two parts are separated by a single space character, each name is all
uppercase letters 'A'-'Z' and gender is a single lowercase letter, either 'm' or 'f'.
Constraints
- data will contain between 1 and 50 elements, inclusive.
- Each element of data will be formatted as above.
- Each element of data will contain between 3 and 50 characters, inclusive.
Examples
0)
{"BOB JOHN","BOB JOHN","BOB MARY","BOB m","AL f"}
Returns: -1
Repeated data elements just give us more confidence. This data is all consistent. BOB's 2 parents are JOHN and MARY (it is not yet known which is the father and which is the mother), and BOB is male. We also know that AL is female.
1)
{"BOB JOHN","BOB MARY","MARY JOHN","JOHN f","MARY f","AL f"}
Returns: 4
The first 4 elements are considered consistent. They describe that BOB's 2 parents are JOHN and MARY and that (unconventionally) MARY is JOHN's child. JOHN is female. But "MARY f" is inconsistent with this since that makes both of BOB's parents female.
2)
{"BOB JOHN", "CARLA BOB", "JOHN CARLA"}
Returns: 2
After the first 2 elements we know that CARLA is a descendant of JOHN, so "JOHN CARLA" cannot be added.
3)
{"BOB RICK", "AL RICK", "AL PAULA", "PAULA LINUS", "LINUS BOB","BOB PAULA"}
Returns: 5
The first 5 elements are consistent. BOB's descendant AL was a child of RICK and PAULA, and RICK is BOB's parent. His other parent could not be PAULA since PAULA is his descendant so the final element is the first one that is inconsistent.
4)
{"BO LESLIE","SUE CASEY","SUE ROBIN","DEE ROBIN","DEE LESLIE","BO CASEY"}
Returns: 5
The final element makes it impossible to assign genders to LESLIE, CASEY, and ROBIN -- if CASEY were male, then ROBIN would have to be female (because of SUE), then LESLIE would have to be male (because of DEE) and then BO would have 2 male parents. Similarly if we assumed CASEY were female we would run into a contradiction.
15)
{"A B","C D","E F","G H","I J","K L","M N","O P","Q R","S T","U V","W X","Y Z","AA AB","AC AD","AE AF","AG AH","AI AJ","AK AL","AM AN","AO AP","AQ AR","AS AT","AU AV"}
Returns: -1
This one breaks anyone who thinks there might be only 50 people (or fewer than 100)
17)
{"NOTTHATHARDACASG NOTTHATHARDACASE","NOTTHATHARDACASG NOTTHATHARDACASF","NOTTHATHARDACASJ NOTTHATHARDACASH","NOTTHATHARDACASJ NOTTHATHARDACASI","NOTTHATHARDACASM NOTTHATHARDACASK","NOTTHATHARDACASM NOTTHATHARDACASL","NOTTHATHARDACASP NOTTHATHARDACASN","NOTTHATHARDACASP NOTTHATHARDACASO","NOTTHATHARDACASS NOTTHATHARDACASQ","NOTTHATHARDACASS NOTTHATHARDACASR","NOTTHATHARDACASV NOTTHATHARDACAST","NOTTHATHARDACASV NOTTHATHARDACASU","NOTTHATHARDACASY NOTTHATHARDACASW","NOTTHATHARDACASY NOTTHATHARDACASX","NOTTHATHARDACATB NOTTHATHARDACASZ","NOTTHATHARDACATB NOTTHATHARDACATA","NOTTHATHARDACATE NOTTHATHARDACATC","NOTTHATHARDACATE NOTTHATHARDACATD","NOTTHATHARDACATH NOTTHATHARDACATF","NOTTHATHARDACATH NOTTHATHARDACATG","NOTTHATHARDACATK NOTTHATHARDACATI","NOTTHATHARDACATK NOTTHATHARDACATJ","NOTTHATHARDACATN NOTTHATHARDACATL","NOTTHATHARDACATN NOTTHATHARDACATM","NOTTHATHARDACATQ NOTTHATHARDACATO","NOTTHATHARDACATQ NOTTHATHARDACATP","NOTTHATHARDACATT NOTTHATHARDACATR","NOTTHATHARDACATT NOTTHATHARDACATS","NOTTHATHARDACATW NOTTHATHARDACATU","NOTTHATHARDACATW NOTTHATHARDACATV","NOTTHATHARDACATZ NOTTHATHARDACATX","NOTTHATHARDACATZ NOTTHATHARDACATY","NOTTHATHARDACAUC NOTTHATHARDACAUA","NOTTHATHARDACAUC NOTTHATHARDACAUB","NOTTHATHARDACAUF NOTTHATHARDACAUD","NOTTHATHARDACAUF NOTTHATHARDACAUE","NOTTHATHARDACAUI NOTTHATHARDACAUG","NOTTHATHARDACAUI NOTTHATHARDACAUH","NOTTHATHARDACAUL NOTTHATHARDACAUJ","NOTTHATHARDACAUL NOTTHATHARDACAUK","NOTTHATHARDACAUO NOTTHATHARDACAUM","NOTTHATHARDACAUO NOTTHATHARDACAUN","NOTTHATHARDACAUR NOTTHATHARDACAUP","NOTTHATHARDACAUR NOTTHATHARDACAUQ","NOTTHATHARDACAUU NOTTHATHARDACAUS","NOTTHATHARDACAUU NOTTHATHARDACAUT","NOTTHATHARDACAUX NOTTHATHARDACAUV","NOTTHATHARDACAUX NOTTHATHARDACAUW","NOTTHATHARDACAVA NOTTHATHARDACAUY","NOTTHATHARDACAVA NOTTHATHARDACAUZ"}
Returns: -1
Slow down people that simply try all assignments.
18)
{"BIGCYCLEBIGCYCLEBIGCYC BIGCYCLEBIGCYCLEBIGCYD","BIGCYCLEBIGCYCLEBIGCYD BIGCYCLEBIGCYCLEBIGCYE","BIGCYCLEBIGCYCLEBIGCYE BIGCYCLEBIGCYCLEBIGCYF","BIGCYCLEBIGCYCLEBIGCYF BIGCYCLEBIGCYCLEBIGCYG","BIGCYCLEBIGCYCLEBIGCYG BIGCYCLEBIGCYCLEBIGCYH","BIGCYCLEBIGCYCLEBIGCYH BIGCYCLEBIGCYCLEBIGCYI","BIGCYCLEBIGCYCLEBIGCYI BIGCYCLEBIGCYCLEBIGCYJ","BIGCYCLEBIGCYCLEBIGCYJ BIGCYCLEBIGCYCLEBIGCYK","BIGCYCLEBIGCYCLEBIGCYK BIGCYCLEBIGCYCLEBIGCYL","BIGCYCLEBIGCYCLEBIGCYL BIGCYCLEBIGCYCLEBIGCYM","BIGCYCLEBIGCYCLEBIGCYM BIGCYCLEBIGCYCLEBIGCYN","BIGCYCLEBIGCYCLEBIGCYN BIGCYCLEBIGCYCLEBIGCYO","BIGCYCLEBIGCYCLEBIGCYO BIGCYCLEBIGCYCLEBIGCYP","BIGCYCLEBIGCYCLEBIGCYP BIGCYCLEBIGCYCLEBIGCYQ","BIGCYCLEBIGCYCLEBIGCYQ BIGCYCLEBIGCYCLEBIGCYR","BIGCYCLEBIGCYCLEBIGCYR BIGCYCLEBIGCYCLEBIGCYS","BIGCYCLEBIGCYCLEBIGCYS BIGCYCLEBIGCYCLEBIGCYT","BIGCYCLEBIGCYCLEBIGCYT BIGCYCLEBIGCYCLEBIGCYU","BIGCYCLEBIGCYCLEBIGCYU BIGCYCLEBIGCYCLEBIGCYV","BIGCYCLEBIGCYCLEBIGCYV BIGCYCLEBIGCYCLEBIGCYW","BIGCYCLEBIGCYCLEBIGCYW BIGCYCLEBIGCYCLEBIGCYX","BIGCYCLEBIGCYCLEBIGCYX BIGCYCLEBIGCYCLEBIGCYY","BIGCYCLEBIGCYCLEBIGCYY BIGCYCLEBIGCYCLEBIGCYZ","BIGCYCLEBIGCYCLEBIGCYZ BIGCYCLEBIGCYCLEBIGCZA","BIGCYCLEBIGCYCLEBIGCZA BIGCYCLEBIGCYCLEBIGCZB","BIGCYCLEBIGCYCLEBIGCZB BIGCYCLEBIGCYCLEBIGCZC","BIGCYCLEBIGCYCLEBIGCZC BIGCYCLEBIGCYCLEBIGCZD","BIGCYCLEBIGCYCLEBIGCZD BIGCYCLEBIGCYCLEBIGCZE","BIGCYCLEBIGCYCLEBIGCZE BIGCYCLEBIGCYCLEBIGCZF","BIGCYCLEBIGCYCLEBIGCZF BIGCYCLEBIGCYCLEBIGCZG","BIGCYCLEBIGCYCLEBIGCZG BIGCYCLEBIGCYCLEBIGCZH","BIGCYCLEBIGCYCLEBIGCZH BIGCYCLEBIGCYCLEBIGCZI","BIGCYCLEBIGCYCLEBIGCZI BIGCYCLEBIGCYCLEBIGCZJ","BIGCYCLEBIGCYCLEBIGCZJ BIGCYCLEBIGCYCLEBIGCZK","BIGCYCLEBIGCYCLEBIGCZK BIGCYCLEBIGCYCLEBIGCZL","BIGCYCLEBIGCYCLEBIGCZL BIGCYCLEBIGCYCLEBIGCZM","BIGCYCLEBIGCYCLEBIGCZM BIGCYCLEBIGCYCLEBIGCZN","BIGCYCLEBIGCYCLEBIGCZN BIGCYCLEBIGCYCLEBIGCZO","BIGCYCLEBIGCYCLEBIGCZO BIGCYCLEBIGCYCLEBIGCZP","BIGCYCLEBIGCYCLEBIGCZP BIGCYCLEBIGCYCLEBIGCZQ","BIGCYCLEBIGCYCLEBIGCZQ BIGCYCLEBIGCYCLEBIGCZR","BIGCYCLEBIGCYCLEBIGCZR BIGCYCLEBIGCYCLEBIGCZS","BIGCYCLEBIGCYCLEBIGCZS BIGCYCLEBIGCYCLEBIGCZT","BIGCYCLEBIGCYCLEBIGCZT BIGCYCLEBIGCYCLEBIGCZU","BIGCYCLEBIGCYCLEBIGCZU BIGCYCLEBIGCYCLEBIGCZV","BIGCYCLEBIGCYCLEBIGCZV BIGCYCLEBIGCYCLEBIGCZW","BIGCYCLEBIGCYCLEBIGCZW BIGCYCLEBIGCYCLEBIGCZX","BIGCYCLEBIGCYCLEBIGCZX BIGCYCLEBIGCYCLEBIGCZY","BIGCYCLEBIGCYCLEBIGCZY BIGCYCLEBIGCYCLEBIGCZZ","BIGCYCLEBIGCYCLEBIGCZZ BIGCYCLEBIGCYCLEBIGCYC"}
Returns: 49
Long cycle.
19)
{"HUGYCLEBIGCYCLEBIGCYD HUGYCLEBIGCYCLEBIGCYC","HUGYCLEBIGCYCLEBIGCYE HUGYCLEBIGCYCLEBIGCYD","HUGYCLEBIGCYCLEBIGCYF HUGYCLEBIGCYCLEBIGCYE","HUGYCLEBIGCYCLEBIGCYG HUGYCLEBIGCYCLEBIGCYF","HUGYCLEBIGCYCLEBIGCYH HUGYCLEBIGCYCLEBIGCYG","HUGYCLEBIGCYCLEBIGCYI HUGYCLEBIGCYCLEBIGCYH","HUGYCLEBIGCYCLEBIGCYJ HUGYCLEBIGCYCLEBIGCYI","HUGYCLEBIGCYCLEBIGCYK HUGYCLEBIGCYCLEBIGCYJ","HUGYCLEBIGCYCLEBIGCYL HUGYCLEBIGCYCLEBIGCYK","HUGYCLEBIGCYCLEBIGCYM HUGYCLEBIGCYCLEBIGCYL","HUGYCLEBIGCYCLEBIGCYN HUGYCLEBIGCYCLEBIGCYM","HUGYCLEBIGCYCLEBIGCYO HUGYCLEBIGCYCLEBIGCYN","HUGYCLEBIGCYCLEBIGCYP HUGYCLEBIGCYCLEBIGCYO","HUGYCLEBIGCYCLEBIGCYQ HUGYCLEBIGCYCLEBIGCYP","HUGYCLEBIGCYCLEBIGCYR HUGYCLEBIGCYCLEBIGCYQ","HUGYCLEBIGCYCLEBIGCYS HUGYCLEBIGCYCLEBIGCYR","HUGYCLEBIGCYCLEBIGCYT HUGYCLEBIGCYCLEBIGCYS","HUGYCLEBIGCYCLEBIGCYU HUGYCLEBIGCYCLEBIGCYT","HUGYCLEBIGCYCLEBIGCYV HUGYCLEBIGCYCLEBIGCYU","HUGYCLEBIGCYCLEBIGCYW HUGYCLEBIGCYCLEBIGCYV","HUGYCLEBIGCYCLEBIGCYX HUGYCLEBIGCYCLEBIGCYW","HUGYCLEBIGCYCLEBIGCYY HUGYCLEBIGCYCLEBIGCYX","HUGYCLEBIGCYCLEBIGCYZ HUGYCLEBIGCYCLEBIGCYY","HUGYCLEBIGCYCLEBIGCZA HUGYCLEBIGCYCLEBIGCYZ","HUGYCLEBIGCYCLEBIGCZB HUGYCLEBIGCYCLEBIGCZA","HUGYCLEBIGCYCLEBIGCZC HUGYCLEBIGCYCLEBIGCZB","HUGYCLEBIGCYCLEBIGCZD HUGYCLEBIGCYCLEBIGCZC","HUGYCLEBIGCYCLEBIGCZE HUGYCLEBIGCYCLEBIGCZD","HUGYCLEBIGCYCLEBIGCZF HUGYCLEBIGCYCLEBIGCZE","HUGYCLEBIGCYCLEBIGCZG HUGYCLEBIGCYCLEBIGCZF","HUGYCLEBIGCYCLEBIGCZH HUGYCLEBIGCYCLEBIGCZG","HUGYCLEBIGCYCLEBIGCZI HUGYCLEBIGCYCLEBIGCZH","HUGYCLEBIGCYCLEBIGCZJ HUGYCLEBIGCYCLEBIGCZI","HUGYCLEBIGCYCLEBIGCZK HUGYCLEBIGCYCLEBIGCZJ","HUGYCLEBIGCYCLEBIGCZL HUGYCLEBIGCYCLEBIGCZK","HUGYCLEBIGCYCLEBIGCZM HUGYCLEBIGCYCLEBIGCZL","HUGYCLEBIGCYCLEBIGCZN HUGYCLEBIGCYCLEBIGCZM","HUGYCLEBIGCYCLEBIGCZO HUGYCLEBIGCYCLEBIGCZN","HUGYCLEBIGCYCLEBIGCZP HUGYCLEBIGCYCLEBIGCZO","HUGYCLEBIGCYCLEBIGCZQ HUGYCLEBIGCYCLEBIGCZP","HUGYCLEBIGCYCLEBIGCZR HUGYCLEBIGCYCLEBIGCZQ","HUGYCLEBIGCYCLEBIGCZS HUGYCLEBIGCYCLEBIGCZR","HUGYCLEBIGCYCLEBIGCZT HUGYCLEBIGCYCLEBIGCZS","HUGYCLEBIGCYCLEBIGCZU HUGYCLEBIGCYCLEBIGCZT","HUGYCLEBIGCYCLEBIGCZV HUGYCLEBIGCYCLEBIGCZU","HUGYCLEBIGCYCLEBIGCZW HUGYCLEBIGCYCLEBIGCZV","HUGYCLEBIGCYCLEBIGCZX HUGYCLEBIGCYCLEBIGCZW","HUGYCLEBIGCYCLEBIGCZY HUGYCLEBIGCYCLEBIGCZX","HUGYCLEBIGCYCLEBIGCZZ HUGYCLEBIGCYCLEBIGCZY","HUGYCLEBIGCYCLEBIGCYC HUGYCLEBIGCYCLEBIGCZZ"}
Returns: 49
A cycle going the other way.
20)
{"A THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCO","A THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCP","B THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCP","B THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCQ","C THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCQ","C THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCR","D THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCR","D THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCS","E THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCS","E THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCT","F THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCT","F THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCU","G THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCU","G THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCV","H THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCV","H THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCW","I THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCW","I THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCX","J THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCX","J THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCY","K THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCY","K THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCZ","L THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCZ","L THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDA","M THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDA","M THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDB","N THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDB","N THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDC","O THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDC","O THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDD","P THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDD","P THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDE","Q THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDE","Q THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDF","R THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDF","R THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDG","S THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDG","S THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDH","T THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDH","T THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDI","U THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDI","U THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDJ","V THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDJ","V THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDK","W THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDK","W THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDL","X THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDL","X THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDM","Y THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDM","Y THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCO"}
Returns: 49
Long names for parents, and also a difficult-to-find parent cycle.
21)
{"A THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCO","A THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCP","B THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCP","B THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCQ","C THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCQ","C THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCR","D THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCR","D THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCS","E THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCS","E THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCT","F THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCT","F THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCU","G THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCU","G THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCV","H THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCV","H THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCW","I THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCW","I THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCX","J THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCX","J THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCY","K THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCY","K THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCZ","L THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCZ","L THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDA","M THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDA","M THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDB","N THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDB","N THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDC","O THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDC","O THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDD","P THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDD","P THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDE","Q THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDE","Q THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDF","R THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDF","R THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDG","S THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDG","S THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDH","T THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDH","T THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDI","U THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDI","U THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDJ","V THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDJ","V THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDK","W THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDK","W THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDL","X THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDL","X THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDM","THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITCO m","THISPARENTHASAVERYVERBOSENAMEWHOKNOWSHOWLONGITDL m"}
Returns: 49
Test a long noncyclic inference chain
22)
{"TESTINGALONGBIGHUGEPROBL TESTINGALONGBIGHUGEPROBM","TESTINGALONGBIGHUGEPROBL TESTINGALONGBIGHUGEPROBN","TESTINGALONGBIGHUGEPROBL TESTINGALONGBIGHUGEPROBO","TESTINGALONGBIGHUGEPROBL TESTINGALONGBIGHUGEPROBP","TESTINGALONGBIGHUGEPROBL TESTINGALONGBIGHUGEPROBQ","TESTINGALONGBIGHUGEPROBL TESTINGALONGBIGHUGEPROBR","TESTINGALONGBIGHUGEPROBL TESTINGALONGBIGHUGEPROBS","TESTINGALONGBIGHUGEPROBL TESTINGALONGBIGHUGEPROBT","TESTINGALONGBIGHUGEPROBL TESTINGALONGBIGHUGEPROBU","TESTINGALONGBIGHUGEPROBM TESTINGALONGBIGHUGEPROBN","TESTINGALONGBIGHUGEPROBM TESTINGALONGBIGHUGEPROBO","TESTINGALONGBIGHUGEPROBM TESTINGALONGBIGHUGEPROBP","TESTINGALONGBIGHUGEPROBM TESTINGALONGBIGHUGEPROBQ","TESTINGALONGBIGHUGEPROBM TESTINGALONGBIGHUGEPROBR","TESTINGALONGBIGHUGEPROBM TESTINGALONGBIGHUGEPROBS","TESTINGALONGBIGHUGEPROBM TESTINGALONGBIGHUGEPROBT","TESTINGALONGBIGHUGEPROBM TESTINGALONGBIGHUGEPROBU","TESTINGALONGBIGHUGEPROBN TESTINGALONGBIGHUGEPROBO","TESTINGALONGBIGHUGEPROBN TESTINGALONGBIGHUGEPROBP","TESTINGALONGBIGHUGEPROBN TESTINGALONGBIGHUGEPROBQ","TESTINGALONGBIGHUGEPROBN TESTINGALONGBIGHUGEPROBR","TESTINGALONGBIGHUGEPROBN TESTINGALONGBIGHUGEPROBS","TESTINGALONGBIGHUGEPROBN TESTINGALONGBIGHUGEPROBT","TESTINGALONGBIGHUGEPROBN TESTINGALONGBIGHUGEPROBU","TESTINGALONGBIGHUGEPROBO TESTINGALONGBIGHUGEPROBP","TESTINGALONGBIGHUGEPROBO TESTINGALONGBIGHUGEPROBQ","TESTINGALONGBIGHUGEPROBO TESTINGALONGBIGHUGEPROBR","TESTINGALONGBIGHUGEPROBO TESTINGALONGBIGHUGEPROBS","TESTINGALONGBIGHUGEPROBO TESTINGALONGBIGHUGEPROBT","TESTINGALONGBIGHUGEPROBO TESTINGALONGBIGHUGEPROBU","TESTINGALONGBIGHUGEPROBP TESTINGALONGBIGHUGEPROBQ","TESTINGALONGBIGHUGEPROBP TESTINGALONGBIGHUGEPROBR","TESTINGALONGBIGHUGEPROBP TESTINGALONGBIGHUGEPROBS","TESTINGALONGBIGHUGEPROBP TESTINGALONGBIGHUGEPROBT","TESTINGALONGBIGHUGEPROBP TESTINGALONGBIGHUGEPROBU","TESTINGALONGBIGHUGEPROBQ TESTINGALONGBIGHUGEPROBR","TESTINGALONGBIGHUGEPROBQ TESTINGALONGBIGHUGEPROBS","TESTINGALONGBIGHUGEPROBQ TESTINGALONGBIGHUGEPROBT","TESTINGALONGBIGHUGEPROBQ TESTINGALONGBIGHUGEPROBU","TESTINGALONGBIGHUGEPROBR TESTINGALONGBIGHUGEPROBS","TESTINGALONGBIGHUGEPROBR TESTINGALONGBIGHUGEPROBT","TESTINGALONGBIGHUGEPROBR TESTINGALONGBIGHUGEPROBU","TESTINGALONGBIGHUGEPROBS TESTINGALONGBIGHUGEPROBT","TESTINGALONGBIGHUGEPROBS TESTINGALONGBIGHUGEPROBU","TESTINGALONGBIGHUGEPROBT TESTINGALONGBIGHUGEPROBU"}
Returns: 2
Illegal because of parent count
23)
{"A B","A C","A B","A C","A m","A m"}
Returns: -1
Test repeated parents, repeated sex
42)
{"Z f", "Y f", "W f", "V f", "X f", "Z A", "Q f", "Z B", "Y B", "Y C", "X C",
"X D", "W D", "W E", "V E", "V F", "Q A", "Q F", "F f", "E m", "U W", "U A",
"X f", "Z A", "Q f"}
Returns: -1
a cycle of parents of length 6 (A - F) F is female --> A is male Also, W and A are parents of U, so they should have different genders. W is female - ok
43)
{"Z f", "Y f", "W f", "V f", "X f", "Z A", "Q f", "Z B", "Y B", "Y C", "X C",
"X D", "W D", "W E", "V E", "V F", "Q A", "Q F", "F m", "E f", "U W", "U A",
"X f", "Z A", "Q f"}
Returns: 21
Similar to 42 a cycle of parents of length 6 (A - F) F is male --> A is female Also, W and A are parents of U, so they should have different genders. W is female - contradiction
Submissions are judged against all 152 archived test cases, of which 15 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FamilyTree with a public method int firstBad(vector<string> data) · 152 test cases · 2 s / 256 MB per case