FriendScore

SRM 436 · 2009-03-11 · by Gluk

SRM 436 · 2009-03-11 · by Gluk · Graph Theory

Show categories

Class Name: FriendScore

Return Type: int

Method Name: highestScore

Arg Types: (vector<string>)

Problem Statement

You want to determine the most popular person in a social network. To do this, you will count the number of "2-friends" that each person has. Person A is called a 2-friend of another person B if they are friends with each other or if there exists some person C who is a friend of both A and B. The most popular person is the person with the highest number of 2-friends. (There might be more than one if multiple people all have the maximal number of 2-friends.)
You are given a String[] friends, where the j-th character of the i-th element is 'Y' if person i and person j are friends, and 'N' otherwise. Return the number of 2-friends of the most popular person in this social network.

Constraints

friends will contain between 1 and 50 elements, inclusive.
Each element of friends will contain exactly N characters 'Y' or 'N', where N is the number of elements in friends.
For each i and j, friends[i][j] will be equal to friends[j][i].
For each i, friends[i][i] will be equal to 'N'.

Examples

{"NNN",
 "NNN",
 "NNN"}
Returns: 0

Here, there are 3 people and none of them are friends, so everybody has zero 2-friends.

{"NYY",
 "YNY",
 "YYN"}
Returns: 2

Each person has two 2-friends.

{"NYNNN",
 "YNYNN", 
 "NYNYN", 
 "NNYNY", 
 "NNNYN"}
Returns: 4

Persons 0 and 4 have two 2-friends, persons 1 and 3 have three 2-friends. Person 2 is the most popular one - four 2-friends.

{"NNNNYNNNNN",
 "NNNNYNYYNN",
 "NNNYYYNNNN",
 "NNYNNNNNNN",
 "YYYNNNNNNY",
 "NNYNNNNNYN",
 "NYNNNNNYNN",
 "NYNNNNYNNN",
 "NNNNNYNNNN",
 "NNNNYNNNNN"}
Returns: 8

{"NNNNNNNNNNNNNNNNNNYNNNNYYYNNNNNNNNNNNNNNYN","NNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNYNNNNNNYNN","NNNNNNNNNNNNNNNNNYNNNYNNNNNNNNNNNNNNNNNNNY","NNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNYNNNYNN","NNNNNYYNNNNNYNNNNNNNNNNNYNNNNNNNNNNNNNNNNN","NNNNYNNNNNNNNYNNNNYNNNNNNNNNNNNNYNNNNYYNNN","NNNNYNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNYNN","NNNNNNNNNNNNNNNNNNNNNNNYNYNYNYNNNNNNNNNNYN","NNNNNNNNNNNNYNNNNNNNNYNNNYNNYNNNNNNNNYNNYN","NNNNNNNNNNYNNNNNNNYNNNNNNNNNNYNNYYNYNNNNNN","NNNNNNNNNYNNNNNNNNNNYNYNNNNNNNNNNYYNNNYNNN","NNNNNNNNNNNNNNYNNNNNNNYNNNNNNNYNNNNNNNNNNN","NNNNYNNNYNNNNNNYYNNNYNNNNNNNNYNNNNNNNNNNNN","NNNNNYNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNY","NNNNNNNNNNNYNNNYNNNNNNNNNNNNNYNNNYYYNNNYNN","NYNNNNNNNNNNYNYNYNNNYNNNNNNNNNNNNYNNNNNNNN","NNNNNNNNNNNNYNNYNNYNNNNNNNNNNNNNNNNNNNNNNN","NNYNNNNNNNNNNNNNNNNNNNYNYNNNNNYNNNNYNYNNYN","YNNNNYNNNYNNNNNNYNNNYNNYNYNNNNNNNYNNNNNNNN","NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNYNN","NNNNNNNNNNYNYNNYNNYNNYNNNNYNNNNNNNNYNNNNNN","NNYNNNNNYNNNNNNNNNNNYNNNNNNNNNYYNYNNNNNNNN","NNNNNNNNNNYYNNNNNYNNNNNNNNNNNYNNNNNNNNNNNN","YNNNNNNYNNNNNNNNNNYNNNNNNNNNNNNNNYNNNNNNNN","YNNNYNYNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNYYNN","YNNNNNNYYNNNNNNNNNYNNNNNNNNNNYNNNNNYYNNNNN","NNNYNNNNNNNNNNNNNNNNYNNNNNNNNYNNNNNNNNNNNN","NNNNNNNYNNNNNNNNNNNNNNNNNNNNYNYYNNNNNNNNYN","NNNNNNNNYNNNNNNNNNNNNNNNNNNYNNNNNNNNNNYNNN","NNNNNNNYNYNNYYYNNNNNNNYNNYYNNNNNNNNNNNNNNN","NNNNNNNNNNNYNNNNNYNNNYNNNNNYNNNNNNNNNNYNNY","NNNNNNNNNNNNNNNNNNNNNYNNNNNYNNNNNNNYNNNNNN","NYNNNYNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNNNYNN","NNNNNNNNNYYNNNYYNNYNNYNYNNNNNNNNNNYNNNNNYN","NNNNNNNNNNYNNNYNNNNNNNNNNNNNNNNNYYNNNNNNNY","NNNYNNNNNYNNNNYNNYNYYNNNNYNNNNNYNNNNNNNNNN","NNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNN","NNNNNYNNYNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNN","NNNNNYNNNNYNNNNNNNNNNNNNYNNNYNYNNNNNNNNNYN","NYNYNNYNNNNNNNYNNNNYNNNNYNNNNNNNYNNNNNNNNN","YNNNNNNYYNNNNNNNNYNNNNNNNNNYNNNNNYNNNNYNNN","NNYNNNNNNNNNNYNNNNNNNNNNNNNNNNYNNNYNNNNNNN"}
Returns: 31

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

Coding Area

Language: C++17 · define a public class FriendScore with a public method int highestScore(vector<string> friends) · 122 test cases · 2 s / 256 MB per case