Statistics

Problem Statement for "DancingCouples"

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

  1. {"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.

  2. {"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}

  3. {"YY", "YY", "YY"}

    3

    Returns: 0

    There are 3 boys but only 2 girls, so it is impossible to select 3 pairs.

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

    3

    Returns: 112

  5. {"Y"}

    1

    Returns: 1

  6. {"Y"}

    3

    Returns: 0

  7. {"N"}

    1

    Returns: 0

  8. {"N"}

    5

    Returns: 0

  9. {"YY"}

    1

    Returns: 2

  10. {"NY"}

    1

    Returns: 1

  11. {"NY"}

    2

    Returns: 0

  12. {"YYNNY"}

    1

    Returns: 3

  13. {"YYYYYYYYYY"}

    1

    Returns: 10

  14. {"YNYYYNNYYY"}

    1

    Returns: 7

  15. {"N", "Y"}

    1

    Returns: 1

  16. {"N", "Y", "Y"}

    1

    Returns: 2

  17. {"N", "Y", "Y"}

    2

    Returns: 0

  18. {"Y", "Y", "Y", "Y", "Y", "Y", "Y", "Y", "Y", "Y"}

    1

    Returns: 10

  19. {"Y", "Y", "N", "N", "Y", "Y", "Y", "N", "Y", "Y"}

    1

    Returns: 7

  20. {"YYNNNNNNNN", "NYYNNNNNNN", "NNYYNNNNNN", "NNNYYNNNNN", "NNNNYYNNNN", "NNNNNYYNNN", "NNNNNNYYNN", "NNNNNNNYYN", "NNNNNNNNYY", "YNNNNNNNNY"}

    1

    Returns: 20

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

  21. {"YYNNNNNNNN", "NYYNNNNNNN", "NNYYNNNNNN", "NNNYYNNNNN", "NNNNYYNNNN", "NNNNNYYNNN", "NNNNNNYYNN", "NNNNNNNYYN", "NNNNNNNNYY", "YNNNNNNNNY"}

    3

    Returns: 800

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

  22. {"YYNNNNNNNN", "NYYNNNNNNN", "NNYYNNNNNN", "NNNYYNNNNN", "NNNNYYNNNN", "NNNNNYYNNN", "NNNNNNYYNN", "NNNNNNNYYN", "NNNNNNNNYY", "YNNNNNNNNY"}

    6

    Returns: 4290

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

  23. {"YYNNNNNNNN", "NYYNNNNNNN", "NNYYNNNNNN", "NNNYYNNNNN", "NNNNYYNNNN", "NNNNNYYNNN", "NNNNNNYYNN", "NNNNNNNYYN", "NNNNNNNNYY", "YNNNNNNNNY"}

    8

    Returns: 825

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

  24. {"YYNNNNNNNN", "NYYNNNNNNN", "NNYYNNNNNN", "NNNYYNNNNN", "NNNNYYNNNN", "NNNNNYYNNN", "NNNNNNYYNN", "NNNNNNNYYN", "NNNNNNNNYY", "YNNNNNNNNY"}

    10

    Returns: 2

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

  25. {"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.

  26. {"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.

  27. {"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.

  28. {"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.

  29. {"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.

  30. {"YYYYNYYYYN", "YYYYNYYYNY", "YYNYYNYYYY", "YYYNYYYYYN", "YYNYNYYYYY", "YYYYYYYYNN", "YYNYYNYYYY", "YYYYNYYYNY", "YYYYNNYYYY", "YNYYYYYYYN"}

    1

    Returns: 80

    Every boy dances with 8 random girls

  31. {"YYNYYYYNYY", "YYYYYYYNNY", "YYNYYYNYYY", "YYYYYNYYYN", "YYNYNYYYYY", "YYYYYYNYYN", "YYYYYNYNYY", "YNYYYYYYNY", "YYYYYNYYNY", "NNYYYYYYYY"}

    2

    Returns: 2595

    Every boy dances with 8 random girls

  32. {"YYYNYYYNYY", "YNYYYYYNYY", "YYYYYNYYYN", "NYYYNYYYYY", "YNYYNYYYYY", "YYYYYNYYYN", "YYNYNYYYYY", "YNYNYYYYYY", "YYYYYNNYYY", "NYYYYYNYYY"}

    3

    Returns: 44442

    Every boy dances with 8 random girls

  33. {"YYNYYYYNYY", "YYYNYYNYYY", "YNYYYYYYNY", "NYNYYYYYYY", "YYYNYYYYYN", "YYYNNYYYYY", "YNYYYYYYNY", "YYNYYNYYYY", "YYYYYYNYYN", "NYYYYYYYNY"}

    4

    Returns: 438439

    Every boy dances with 8 random girls

  34. {"YYYYYYNYNY", "YYYYYYYYNN", "YYYYNYYYYN", "YYYYNYNYYY", "YYYNYYYYYN", "YYYNYYYYNY", "YYNYYYYYYN", "YNYYYYYYNY", "NYYYYYYYYN", "YNYYYYNYYY"}

    5

    Returns: 2459880

    Every boy dances with 8 random girls

  35. {"YYYNYNYYYY", "YNNYYYYYYY", "YNNYYYYYYY", "YYYYYYNNYY", "YYYYNYYYYN", "YYNYYYNYYY", "YYYYYNNYYY", "NYNYYYYYYY", "YNNYYYYYYY", "YYYNYYNYYY"}

    6

    Returns: 8174829

    Every boy dances with 8 random girls

  36. {"YYYYNYYYYN", "YNYYYYYYNY", "YYYNYYYNYY", "NYYYYYYNYY", "YYYYNNYYYY", "NYYNYYYYYY", "YYYYYNNYYY", "YYYYNNYYYY", "YNYYNYYYYY", "YNYYYYYNYY"}

    7

    Returns: 15365766

    Every boy dances with 8 random girls

  37. {"NYNYYYYYYY", "YYYYNYYYNY", "YNYNYYYYYY", "YYYYYNYNYY", "YYYNYYYYYN", "NNYYYYYYYY", "YNYNYYYYYY", "YNYYYYNYYY", "YYYYYYNNYY", "NYYYNYYYYY"}

    8

    Returns: 14101790

    Every boy dances with 8 random girls

  38. {"NYNYYYYYYY", "YYYYNYYYYN", "NYYYYYYNYY", "YYNYNYYYYY", "YYYYYYNYNY", "NYNYYYYYYY", "YYNYYYNYYY", "NYYYYYYNYY", "YNYYYNYYYY", "YYYNYYYYYN"}

    9

    Returns: 4972428

    Every boy dances with 8 random girls

  39. {"YYYYYNNYYY", "YYYYNYYYNY", "YYYYYNYYNY", "YNYYYNYYYY", "YYYYNNYYYY", "YYYYYYYNNY", "YYYYNYYYYN", "YYYNYYYNYY", "NYYNYYYYYY", "YYYYYYYNNY"}

    10

    Returns: 385314

    Every boy dances with 8 random girls

  40. {"YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY"}

    1

    Returns: 100

    Every boy can dance with every girl

  41. {"YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY"}

    2

    Returns: 4050

    Every boy can dance with every girl

  42. {"YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY"}

    8

    Returns: 81648000

    Every boy can dance with every girl

  43. {"YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY"}

    9

    Returns: 36288000

    Every boy can dance with every girl

  44. {"YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY"}

    10

    Returns: 3628800

    Every boy can dance with every girl

  45. {"YNYNYYYNYY", "NNYYYNNYYY", "NYNNNYYYYY", "YYYYYNNYYN", "YYNNYYNNYY", "YNYYYYYYNY", "YYYYYYYYYY" }

    5

    Returns: 115958

  46. {"YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY" }

    10

    Returns: 3628800

  47. {"YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY" }

    5

    Returns: 7620480

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

    3

    Returns: 112

  49. {"YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYNYYY", "YYYYYYYYNY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY" }

    8

    Returns: 69148800

  50. {"YYYY", "YYYY", "YYYY" }

    3

    Returns: 24

  51. {"YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY" }

    8

    Returns: 81648000

  52. {"YYYYYYYYYY", "NYYYYYYYYY", "YNYYYYYYYY", "YYNYYYYYYY", "YYYNYYYYYY", "YYYYNYYYYY", "YYYYYNYYYY", "YYYYYYNYYY", "YYYYYYYNYY", "YYYYYYYYNY" }

    9

    Returns: 16019531

  53. {"YYY", "YYY", "YYY" }

    10

    Returns: 0

  54. {"YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY" }

    4

    Returns: 1058400

  55. {"Y" }

    3

    Returns: 0

  56. {"YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY", "YYYYYYYYYY" }

    9

    Returns: 36288000

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.
This problem was used for: