TopCoder problem "PeopleYouMayKnow" used in SRM 447 (Division I Level Two)



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.

 

Definition

    
Class:PeopleYouMayKnow
Method:maximalScore
Parameters:String[], int, int
Returns:int
Method signature:int maximalScore(String[] friends, int person1, int person2)
(be sure your method is public)
    
 

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

0)
    
{"NN"
,"NN"}
0
1
Returns: 0
You don't need to remove any people.
1)
    
{"NYNN"
,"YNYN"
,"NYNY"
,"NNYN"}
0
3
Returns: 1
You need to remove person 1 or person 2.
2)
    
{"NYNYYYN"
,"YNYNNYY"
,"NYNNNNY"
,"YNNNNNN"
,"YNNNNYN"
,"YYNNYNY"
,"NYYNNYN"}
2
3
Returns: 1
You need to remove person 0 or person 1.
3)
    
{"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).

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10580

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13901&pm=10580

Writer:

Gluk

Testers:

PabloGilberto , ivan_metelsky , ged

Problem categories:

Graph Theory