PeopleYouMayKnow

SRM 447 · 2009-08-25 · by Gluk

SRM 447 · 2009-08-25 · by Gluk · Graph Theory

Show categories

Class Name: PeopleYouMayKnow

Return Type: int

Method Name: maximalScore

Arg Types: (vector<string>, int, int)

Problem Statement

Tim wants to improve "People You May Know" feature of Facebook. This is a feature that attempts to automatically connect people who may know each other in reality, but haven't yet added each other as friends on Facebook.

Friendship on Facebook is symmetric, meaning that if B is a friend of A, then A is also a friend of B. However, it is not necessarily transitive, so if A and B are friends and B and C are friends, then A and C are not necessarily friends.

Tim has defined the term "n-friends" as follows. If two people are friends, they are called 1-friends. For n >= 1, two people A and B are called (n+1)-friends if A and B are n-friends, or if there exists a person C such that A and C are n-friends and C and B are friends.

To determine how likely it is that two people know each other, Tim has introduced the concept of a "Distance Score". If two people A and B are not friends, then their Distance Score is the fewest number of people (other than A and B themselves) who must be removed from the network in order for A and B to not be 3-friends. The higher the Distance Score, the more likely it is that A and B know each other.

You are given String[] friends containing exactly N elements, where N is the number of people in the network. People are numbered from 0 to N-1. The j-th character of the i-th element of friends is 'Y' if i and j are friends, and 'N' otherwise. Return the Distance Score for person1 and person2.

Constraints

friends will contain N elements, where N is between 2 and 40, inclusive.
Each element of friends will contain exactly N characters.
Each character in friends will be 'Y' or 'N'.
For all i and j, friends[i][j] will be equal to friends[j][i].
For all i, friends[i][i] will be equal to 'N'.
person1 and person2 will each be between 0 and N-1, inclusive.
person1 and person2 will not be equal.
friends[person1][person2] will be equal to 'N'.

Examples

{"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"YNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NYYYYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNNNY",
"NNNNNNNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYN"}
0
39
Returns: 19

{"NNYY", "NNYN", "YYNY", "YNYN"}
1
3
Returns: 1

{"NNNYYNNNNYNNNYNNYNYNNNYN","NNNNNYNNNNNNNNNYYNNNYNNN","NNNNNNNYNNNNYYNNYNNYNNNY","YNNNNYNNNNNNNNNNNYYYNNNN","YNNNNNNNNNNNNNYYYNNNNNYY","NYNYNNYYNNNNYNYNNNNNNNYN","NNNNNYNNNYYNYYNNYYNNNNNY","NNYNNYNNYNNNNNNNNNNYNNNY","NNNNNNNYNNYNYNYNNNNYNNYN","YNNNNNYNNNNNYYNNNNYNYNNN","NNNNNNYNYNNNNYNNYNNNNNYN","NNNNNNNNNNNNNNNYNNNYNYNN","NNYNNYYNYYNNNYNYYNYNYNNN","YNYNNNYNNYYNYNNNNNNNNYNN","NNNNYYNNYNNNNNNNYNNNNNNY","NYNNYNNNNNNYYNNNYYNYNNNN","YYYNYNYNNNYNYNYYNYNNYNNN","NNNYNNYNNNNNNNNYYNNNYNNY","YNNYNNNNNYNNYNNNNNNNNNNY","NNYYNNNYYNNYNNNYNNNNNYNN","NYNNNNNNNYNNYNNNYYNNNNYN","NNNNNNNNNNNYNYNNNNNYNNYY","YNNNYYNNYNYNNNNNNNNNYYNN","NNYNYNYYNNNNNNYNNYYNNYNN"}
8
15
Returns: 4

{"NYNYNNNNYNYNYNYYNYNYYYNYNNNNNYYYYYYNYYYN","YNNYYYNYNYYYNYNYYNYYYNYNNYNNNYYYYYYNNYNY","NNNNYYYNNNYYNNNNNNNYYYYYNNNNNNNNNNYYYNNN","YYNNNNYNNYYYNNNYYYYNYNNNYYYNYNYYNYNYYYYY","NYYNNYYNNNNNNYYYNYYNNNNNYYNNNYYNYYYYNYNN","NYYNYNYYYNYYNNNNYYNNNYYYNYNYYYYYYNNYNYNN","NNYYYYNNYNNNYYNNNNYNNNYYYYNYNNYYYNYYNYYN","NYNNNYNNYNYNYNYNYYNYNNNYYYNNNYNYYNNNYNNY","YNNNNYYYNYNNNYYYNYNNYNNNYYNNYNNYYYYNNYNY","NYNYNNNNYNNYNNYNNYNNYNYYNNNNNYNYNNYNYYYN","YYYYNYNYNNNNNYNNYYNYNYYNYNYYNNYNYYYYNYYY","NYYYNYNNNYNNYNNYYNYYYNNNYNNNYYYNYNYNNNYY","YNNNNNYYNNNYNNNNNNYNYNNYNYNYYNYYYNNYYYNY","NYNNYNYNYNYNNNNYYNNYNNYNYNNYNNNNNYNNYYYN","YNNNYNNYYYNNNNNNYNYNYYYYYYYNNYNNNNYNNNNN","YYNYYNNNYNNYNYNNYNNNYYNYYYNNYYNYYNYYNYYY","NYNYNYNYNNYYNYYYNNNYNNNYNYNNYNYNYNNYYYNN","YNNYYYNYYYYNNNNNNNNYYNYNYYNNYYYNNNNYNNYN","NYNYYNYNNNNYYNYNNNNNYYNNYYYYNYYNYNYNNNYN","YYYNNNNYNNYYNYNNYYNNNYNYNYNYYNYNYNYYNYNN","YYYYNNNNYYNYYNYYNYYNNYYYYNYYNNNNYYYNYYNY","YNYNNYNNNNYNNNYYNNYYYNNNYYYNNYYYYYNYNYYN","NYYNNYYNNYYNNYYNNYNNYNNYYNNYYNYYNYNNNYNN","YNYNNYYYNYNNYNYYYNNYYNYNYNYNNNNNNNNYYNYY","NNNYYNYYYNYYNYYYNYYNYYYYNYYYYNYYNYYYYNNN","NYNYYYYYYNNNYNYYYYYYNYNNYNYYNNYYNYYNYYYN","NNNYNNNNNNYNNNYNNNYNYYNYYYNYNYNYYNYYNYNY","NNNNNYYNNNYNYYNNNNYYYNYNYYYNYYNNYNYYNYYN","NNNYNYNNYNNYYNNYYYNYNNYNYNNYNYNNNYNNYNNY","YYNNYYNYNYNYNNYYNYYNNYNNNNYYYNNYNYNNNYNY","YYNYYYYNNNYYYNNNYYYYNYYNYYNNNNNYNYNYYYYN","YYNYNYYYYYNNYNNYNNNNNYYNYYYNNYYNNNNYYNYN","YYNNYYYYYNYYYNNYYNYYYYNNNNYYNNNNNYYYNYNY","YYNYYNNNYNYNNYNNNNNNYYYNYYNNYYYNYNNYNNNN","YYYNYNYNYYYYNNYYNNYYYNNNYYYYNNNNYNNYNYYY","NNYYYYYNNNYNYNNYYYNYNYNYYNYYNNYYYYYNNYYY","YNYYNNNYNYNNYYNNYNNNYNNYYYNNYNYYNNNNNNYY","YYNYYYYNYYYNYYNYYNNYYYYNNYYYNYYNYNYYNNNN","YNNYNNYNNYYYNYNYNYYNNYNYNYNYNNYYNNYYYNNY","NYNYNNNYYNYYYNNYNNNNYNNYNNYNYYNNYNYYYNYN"}
7
6
Returns: 17

{"NYNNNYNYYNYYNYYNYNYYYYYNNNNYNNYNNYY","YNYNYNNNYYNYYNYNNNYYNNNYYNNNNYYNYNN","NYNNNYYYYYYNNNNYNNNYYNNNNYNYYNYYYNN","NNNNYNNNNNYNYNNNNYNYNYNNYYYYNYNYNNY","NYNYNYNNYYYYYNNYNNNNYNNNNNNYNNYNNYY","YNYNYNNYNNNNNNYYNNYYNNNNNNYYNNNYNNN","NNYNNNNNNYYNNNYNNYNNNNYNNNNNNYYYNNN","YNYNNYNNNNYYNYYNNYYYNYNNNNNYYYYYYNY","YYYNYNNNNYYNNYYNNYYYYNNNYNYNNNYNYYN","NYYNYNYNYNYNNYNYNYNNYYNYNYYYYNYYNNY","YNYYYNYYYYNYNYNNNNYYNYNYNNNNYNNNYYN","YYNNYNNYNNYNYNYYYYNNYNYNNYYNNYNNNNN","NYNYYNNNNNNYNNYYNYYYYYNYNYNYYYYNNNY","YNNNNNNYYYYNNNNNNNNNYNYYNNYYYNYNYNY","YYNNNYYYYNNYYNNNYNYYNYNNYNYNNNYNYYN","NNYNYYNNNYNYYNNNNYYYNNNNYNNYYYNNYNY","YNNNNNNNNNNYNNYNNNYNNNNYNYNYYYYNYYN","NNNYNNYYYYNYYNNYNNNNNNYYYNYYYYYNYYN","YYNNNYNYYNYNYNYYYNNNYNYNYYYYYNNYNYY","YYYYNYNYYNYNYNYYNNNNNNYNYYNYNYYYNNY","YNYNYNNNYYNYYYNNNNYNNNNYNNYYYNYNNYN","YNNYNNNYNYYNYNYNNNNNNNNYNNYNYYNYNNY","YNNNNNYNNNNYNYNNNYYYNNNNNYYYYYNNYYN","NYNNNNNNNYYNYYNNYYNNYYNNNNYYYYYNNNN","NYNYNNNNYNNNNNYYNYYYNNNNNYNYYNYYNNN","NNYYNNNNNYNYYNNNYNYYNNYNYNYYNNNNNNY","NNNYNYNNYYNYNYYNNYYNYYYYNYNYNYNYNNY","YNYYYYNYNYNNYYNYYYYYYNYYYYYNNYYYNNY","NNYNNNNYNYYNYYNYYYYNYYYYYNNNNNNNNNY","NYNYNNYYNNNYYNNYYYNYNYYYNNYYNNNYNNY","YYYNYNYYYYNNYYYNYYNYYNNYYNNYNNNNYNY","NNYYNYYYNYNNNNNNNNYYNYNNYNYYNYNNNNN","NYYNNNNYYNYNNYYYYYNNNNYNNNNNNNYNNYY","YNNNYNNNYNYNNNYNYYYNYNYNNNNNNNNNYNN","YNNYYNNYNYNNYYNYNNYYNYNNNYYYYYYNYNN"}
0
12
Returns: 18

51)

{"NN"
,"NN"}
0
1
Returns: 0

You don't need to remove any people.

52)

{"NYNN"
,"YNYN"
,"NYNY"
,"NNYN"}
0
3
Returns: 1

You need to remove person 1 or person 2.

53)

{"NYNYYYN"
,"YNYNNYY"
,"NYNNNNY"
,"YNNNNNN"
,"YNNNNYN"
,"YYNNYNY"
,"NYYNNYN"}
2
3
Returns: 1

You need to remove person 0 or person 1.

54)

{"NYYYYNNNN"
,"YNNNNYYYN"
,"YNNNNNNYN"
,"YNNNNNNYN"
,"YNNNNNNNY"
,"NYNNNNNNY"
,"NYNNNNNNY"
,"NYYYNNNNY"
,"NNNNYYYYN"}
8
0
Returns: 3

You need to remove person 4 (who knows both 0 and 8), person 1 (friend of 0) and person 7 (friend of 8).

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

Coding Area

Language: C++17 · define a public class PeopleYouMayKnow with a public method int maximalScore(vector<string> friends, int person1, int person2) · 209 test cases · 2 s / 256 MB per case