TopCoder problem "DancingCouples" used in SRM 416 (Division II Level Three)



Problem Statement

    

There are N boys and M girls in a dance school. The teachers are organizing a performance and they need exactly K boy-girl couples for their show. Unfortunately, this is not a straightforward task since some children cannot be paired with each other (due to differences in height, skill, etc.). One of the teachers is a computer science graduate, and has decided to count the number of ways to select K couples.

You are given a String[] canDance containing exactly N elements, each with exactly M characters. The j-th character of the i-th element of canDance is 'Y' if boy i can be paired with girl j, and 'N' otherwise. Return the number of distinct valid ways to select exactly K boy-girl pairs.

 

Definition

    
Class:DancingCouples
Method:countPairs
Parameters:String[], int
Returns:int
Method signature:int countPairs(String[] canDance, int K)
(be sure your method is public)
    
 

Constraints

-canDance will contain between 1 and 10 elements, inclusive.
-Each element of canDance will contain between 1 and 10 characters, inclusive.
-Each element of canDance will contain the same number of characters.
-Each character in canDance will be either 'Y' or 'N'.
-K will be between 1 and 10, inclusive.
 

Examples

0)
    
{"YYYY", 
 "YYYY",
 "YYYY"}
3
Returns: 24
There are three boys and four girls. Every boy can dance with every girl. The first boy selects one of the four girls, the second boy selects one of the three remaining girls, and the third boy selects one of the two remaining girls. Thus, there are 4*3*2=24 ways to create three couples.
1)
    
{"YYNN", 
 "NYYN", 
 "NNYY"}
3
Returns: 4
There are 4 possible pairings:

{boy1-girl1, boy2-girl2, boy3-girl3},

{boy1-girl1, boy2-girl2, boy3-girl4},

{boy1-girl1, boy2-girl3, boy3-girl4},

{boy1-girl2, boy2-girl3, boy3-girl4}
2)
    
{"YY", 
 "YY", 
 "YY"}
3
Returns: 0
There are 3 boys but only 2 girls, so it is impossible to select 3 pairs.
3)
    
{"YYNNNN",
 "NYYNNN",
 "NNYYNN",
 "NNNYYN",
 "NNNNYY",
 "YNNNNY"}
3
Returns: 112

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13507&pm=9902

Writer:

xOberon

Testers:

PabloGilberto , Olexiy , ivan_metelsky , zhuzeyuan

Problem categories:

Dynamic Programming, Graph Theory