TopCoder problem "DancingParty" used in SRM 399 (Division I Level Three)



Problem Statement

    

You are organizing a dance party. The party will be attended by n boys and n girls. There will be several rounds of dancing.

In each round, you divide the guests into n dancing pairs. Each guest must be in exactly one pair, and each pair must contain one boy and one girl. Each boy must dance with a different girl in every round. Some boys and girls like each other and some do not. During the party, each boy agrees to dance with at most k girls he doesn't like. Similarly, each girl agrees to dance with at most k boys she doesn't like.

You are given a String[] likes. The j-th character of likes[i] is 'Y' if the i-th boy and the j-th girl like each other, and 'N' if they don't. Return the maximum number of rounds you can organize.

 

Definition

    
Class:DancingParty
Method:maxDances
Parameters:String[], int
Returns:int
Method signature:int maxDances(String[] likes, int k)
(be sure your method is public)
    
 

Constraints

-likes will contain between 1 and 50 elements, inclusive.
-Each element of likes will contain exactly n characters, where n is the number of elements in likes.
-Each element of likes will contain only the characters 'Y' and 'N'.
-k will be between 0 and 50, inclusive.
 

Examples

0)
    
{"YYY", "YYY", "YYY"}
0
Returns: 3
Every boy likes every girl, so you can organize 3 rounds.
1)
    
{"YYY", "YYN", "YNY"}
0
Returns: 2
For example, you can have one round with pairs 1-2, 2-1 and 3-3 and one round with pairs 1-3, 2-2 and 3-1.
2)
    
{"YN", "YN"}
0
Returns: 0
The second girl doesn't like anybody.
3)
    
{"YN", "YN"}
1
Returns: 1
The second girl doesn't like anybody again, but this time she agrees to dance with someone she doesn't like once.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12171&pm=8754

Writer:

andrewzta

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Graph Theory