TopCoder problem "TeamManagement" used in SRM 421 (Division I Level Three)



Problem Statement

    

You are the manager of a newly formed football club and want to buy some players for your club. You identified that there are N potentially interesting players on the market and numbered them 0 to N-1. You don't have enough money to buy all these players, so you want to buy only K of them.

It appears however that buying players is not always easy. Some of the players are loyal to your club. To buy such a player you can just pay money for him. Other players are not loyal, and you can buy such a player A only if you have previously bought some player B, who is a friend of player A.

You are given a String loyalty, where the i-th character is 'Y' if the i-th player is loyal to your club, and is 'N' otherwise. You are also given a String[] friends, which describes which pairs of players are friends of each other. Each element has the format "A B", where A and B are the numbers of two players who are the friends of each other.

Friendship is symmetrical (if A is a friend of B, then B is a friend of A) and not necessarily transitive (if A is a friend of B and B is a friend of C, then C is not necessarily a friend of A). It is known that friends contains exactly N-1 elements and that for any two players A and B there exists a chain of players with numbers I0=A, I1, ..., Ik-1, Ik=B (k >= 1), where every two players consecutive in the chain are friends of each other (we'll call this property a connectedness of friendship relation). It is guaranteed that each player has at most 3 friends and that at least one player is loyal to your club.

A subset of K players is called possible if you can buy all players from this subset and only these players, in some order. You decided to choose some possible subset and to buy all players from it. If there are many such subsets, you choose one at random (all subsets have the same probability of being chosen).

You are now interested in the probability of buying each of the players. Return a double[] containing N elements, where the i-th element is the probability of buying the i-th player.

 

Definition

    
Class:TeamManagement
Method:getDistribution
Parameters:int, int, String[], String
Returns:double[]
Method signature:double[] getDistribution(int N, int K, String[] friends, String loyalty)
(be sure your method is public)
    
 

Notes

-Each element of your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-N will be between 1 and 50, inclusive.
-K will be between 1 and N, inclusive.
-loyalty will contain exactly N characters.
-Each character of loyalty will be 'Y' or 'N'.
-At least one character of loyalty will be 'Y'.
-friends will contain exactly N-1 elements.
-Each element of friends will be formatted "A B" (quotes for clarity), where A and B are distinct integers between 0 and N-1, inclusive, with no extra leading zeros.
-The friendship relation will be connected (see the statement for precise definition).
-Each player will have at most 3 friends.
 

Examples

0)
    
5
3
{"0 1", "1 2", "2 3", "3 4"}
"NNYNN"
Returns: 
{0.33333333333333337, 0.6666666666666667, 1.0, 0.6666666666666667, 0.33333333333333337 }
There are three possible subsets: {0, 1, 2}, {1, 2, 3} and {2, 3, 4}.
1)
    
4
3
{"2 0", "2 1", "2 3"}
"NNYN"
Returns: {0.6666666666666667, 0.6666666666666667, 1.0, 0.6666666666666667 }
All subsets that include player 2 are possible.
2)
    
6
4
{"4 3", "3 1", "3 0", "0 2", "0 5"}
"NNNNYY"
Returns: 
{0.8571428571428572, 0.4285714285714286, 0.4285714285714286, 0.8571428571428572, 0.7142857142857143, 0.7142857142857143 }
The following 7 subsets are possible in this case: {1, 3, 4, 5}, {0, 3, 4, 5}, {0, 2, 4, 5}, {0, 2, 3, 5}, {0, 2, 3, 4}, {0, 1, 3, 5}, {0, 1, 3, 4}.
3)
    
6
1
{"3 0", "0 2", "0 4", "4 1", "2 5"}
"YYYNNN"
Returns: {0.33333333333333337, 0.33333333333333337, 0.33333333333333337, 0.0, 0.0, 0.0 }
When you wish to buy only one player, it must be a loyal player.
4)
    
7
7
{"3 1", "1 5", "5 4", "4 0", "4 6", "5 2"}
"NNNNNNY"
Returns: {1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0 }
Here you wish to buy all available players.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13512&pm=10107

Writer:

ivan_metelsky

Testers:

PabloGilberto , Yarin , Olexiy

Problem categories:

Dynamic Programming