DancingCouples | Topcoder Archive

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

```
{"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.
```
{"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}
```
{"YY", 
 "YY", 
 "YY"}
```
```
3
```
```
Returns: 0
```
There are 3 boys but only 2 girls, so it is impossible to select 3 pairs.

{"YYNNNN",
 "NYYNNN",
 "NNYYNN",
 "NNNYYN",
 "NNNNYY",
 "YNNNNY"}

Returns: 112

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.