DancingCouples

SRM 416 · 2008-09-03 · by xOberon

SRM 416 · 2008-09-03 · by xOberon · Dynamic Programming, Graph Theory

Show categories

Class Name: DancingCouples

Return Type: int

Method Name: countPairs

Arg Types: (vector<string>, int)

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.

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"}
3
Returns: 112

{"Y"}
1
Returns: 1

19)

{"YYNNNNNNNN", "NYYNNNNNNN", "NNYYNNNNNN", "NNNYYNNNNN", "NNNNYYNNNN", "NNNNNYYNNN", "NNNNNNYYNN", "NNNNNNNYYN", "NNNNNNNNYY", "YNNNNNNNNY"}
1
Returns: 20

Boy i can dance with Girls i and i+1.

20)

{"YYNNNNNNNN", "NYYNNNNNNN", "NNYYNNNNNN", "NNNYYNNNNN", "NNNNYYNNNN", "NNNNNYYNNN", "NNNNNNYYNN", "NNNNNNNYYN", "NNNNNNNNYY", "YNNNNNNNNY"}
3
Returns: 800

Boy i can dance with Girls i and i+1.

21)

{"YYNNNNNNNN", "NYYNNNNNNN", "NNYYNNNNNN", "NNNYYNNNNN", "NNNNYYNNNN", "NNNNNYYNNN", "NNNNNNYYNN", "NNNNNNNYYN", "NNNNNNNNYY", "YNNNNNNNNY"}
6
Returns: 4290

Boy i can dance with Girls i and i+1.

22)

{"YYNNNNNNNN", "NYYNNNNNNN", "NNYYNNNNNN", "NNNYYNNNNN", "NNNNYYNNNN", "NNNNNYYNNN", "NNNNNNYYNN", "NNNNNNNYYN", "NNNNNNNNYY", "YNNNNNNNNY"}
8
Returns: 825

Boy i can dance with Girls i and i+1.

23)

{"YYNNNNNNNN", "NYYNNNNNNN", "NNYYNNNNNN", "NNNYYNNNNN", "NNNNYYNNNN", "NNNNNYYNNN", "NNNNNNYYNN", "NNNNNNNYYN", "NNNNNNNNYY", "YNNNNNNNNY"}
10
Returns: 2

Boy i can dance with Girls i and i+1.

24)

{"YYNYYNNNYN", "NYYYNNYNYN", "NNYYYNYNNY", "NYNYYNNYNY", "NNNYYYNYYN", "NYYNYYYNNN", "NNYNYNYYYN", "YNNYYNNYYN", "NYNNYNYNYY", "YYYNNNYNNY"}
1
Returns: 50

Boy i can dance with Girls i and i+1 and 3 other random girls.

25)

{"YYNNNYYNYN", "NYYNNYYYNN", "YNYYNYNNNY", "YYNYYNYNNN", "YNYNYYNNYN", "NNYYYYYNNN", "NYNYNYYYNN", "NNNYNYNYYY", "NNNNYYNYYY", "YYYNNYNNNY"}
3
Returns: 10900

Boy i can dance with Girls i and i+1 and 3 other random girls.

26)

{"YYNNNYYNNY", "YYYYNNYNNN", "NYYYNNNYNY", "NYNYYYNNYN", "NYNNYYYNYN", "YNYNYYYNNN", "YNYNNNYYYN", "NYNYNNYYYN", "NNYNNYYNYY", "YNYNNYNYNY"}
5
Returns: 251268

Boy i can dance with Girls i and i+1 and 3 other random girls.

27)

{"YYNYNNNNYY", "YYYYNNNYNN", "NNYYYYNYNN", "YNNYYNYNYN", "NYYNYYNNYN", "NNYNNYYYNY", "NNNNYYYYNY", "NNNYYNYYYN", "NYNYNNNYYY", "YNYNYYNNNY"}
7
Returns: 683782

Boy i can dance with Girls i and i+1 and 3 other random girls.

28)

{"YYNYYNNNYN", "NYYYNNNYYN", "NNYYYYNNNY", "YNYYYNNYNN", "YNNNYYYNNY", "YYNNNYYNYN", "YNNYNNYYYN", "NYNNYNYYYN", "YNYNNNNYYY", "YYNYYNNNNY"}
10
Returns: 4410

Boy i can dance with Girls i and i+1 and 3 other random girls.

29)

{"YYYYNYYYYN", "YYYYNYYYNY", "YYNYYNYYYY", "YYYNYYYYYN", "YYNYNYYYYY", "YYYYYYYYNN", "YYNYYNYYYY", "YYYYNYYYNY", "YYYYNNYYYY", "YNYYYYYYYN"}
1
Returns: 80