Statistics

Problem Statement for "TennisRallies"

Problem Statement

You are practicing your tennis game with a hitting partner. Each time the ball comes over the net a player can either hit it cross-court, or down-the-line. In this problem, a sequence of shots will be denoted by a String composed of (quotes for clarity) the letters 'c' and 'd', representing cross-court and down-the-line shots respectively. For example, "cccddc" would be such a sequence consisting of 3 cross-courts, 2 down-the-lines, and a final cross-court.

Since you are going to practice a particular play strategy there are certain shot sequences you will avoid. You are given a String[] forbidden containing precisely which sequences must be avoided. For example, if (quotes for clarity) "ccd" is an element of forbidden then you should never allow 2 cross-court shots followed by a down-the-line shot to occur consecutively at any point in the rally. If you were a professional, a single forbidden sequence might cause you to stop hitting. Since you are an amateur, you are willing to let allowed distinct forbidden sequences to occur before you stop. For example, if allowed was 2, the second forbidden sequence would terminate the hitting sequence.

You will return the number of distinct hitting sequences of length numLength which contain fewer than allowed forbidden sequences. Two hitting sequences are distinct if they differ at some stroke in the sequence. Two forbidden sequences are distinct if they differ in length, or position in the hitting sequence they begin at. For example, if forbidden = {"cc","cd","ccd"} then the sequence "ccccdd" has 5 distinct forbidden sequences (3 distinct "cc" sequences, a "cd" sequence, and a "ccd" sequence).

Definition

Class:
TennisRallies
Method:
howMany
Parameters:
int, String[], int
Returns:
int
Method signature:
int howMany(int numLength, String[] forbidden, int allowed)
(be sure your method is public)

Constraints

  • numLength will be between 1 and 18 inclusive
  • forbidden will contain between 0 and 10 elements inclusive
  • allowed will be between 1 and 100 inclusive
  • forbidden will contain no repeated elements
  • Each element of forbidden will contain between 1 and 18 'c's and 'd's inclusive (quotes for clarity; both are lowercase)

Examples

  1. 3

    {"cc","dd"}

    1

    Returns: 2

    Since allowed is 1, neither "cc" nor "dd" can occur anywhere in a valid sequence. The only possible sequences are thus "cdc" and "dcd".

  2. 10

    {"c"}

    1

    Returns: 1

    There is exactly 1 sequence with 10 shots that contains no cross-court shots.

  3. 10

    {"c"}

    2

    Returns: 11

    There are 11 sequences that contain at most 1 cross-court shot.

  4. 18

    {"c","d"}

    1

    Returns: 0

  5. 18

    {"c","cc","ccc","cccc","ccccc","cccccc","ccccccc", "cccccccc","ccccccccc","cccccccccc"}

    20

    Returns: 185406

  6. 18

    {"ccccccccccc", "cccccccccccc", "ccccccccccccc", "cccccccccccccc", "ccccccccccccccc", "cccccccccccccccc", "ccccccccccccccccc", "cccccccccccccccccc" }

    100

    Returns: 262144

  7. 18

    {}

    1

    Returns: 262144

  8. 18

    {"c","cc","ccc","cccc","ccccc","cccccc","ccccccc", "cccccccc","ccccccccc","cccccccccc"}

    100

    Returns: 262122

  9. 18

    {"dcccc","cdcdc","dcdcc","dccdc","ddcdd","cccdd","dcccd","dcdcd","cddcd","dccdd"}

    100

    Returns: 262144

  10. 18

    {"c","d","cc","cd","dd","dc","ccc","ccd","cdc","cdd"}

    40

    Returns: 10068

  11. 17

    {"cdccdddccddcdcd","ccdcddcd","cddcddddccdcc","cddddcdcddcdccddd","dddddc","d","ddddccdcdc","dcdccccdddc","dddccddccc","dc"}

    25

    Returns: 131072

  12. 15

    {"ddcdddddccc","d","cdccc","dddddcdcdddcddcd","ddccdcd","dcddddcccccddcdd","ccdcdc","dccd","cccccddd","dddddc"}

    24

    Returns: 32768

  13. 14

    {"dccccdddddcd","dddddcccdccd","cdddcdcccdcdcddd","dd","dcccccdddcd","cccddcc","dddcccdcddcdccccdd"}

    9

    Returns: 16209

  14. 17

    {"cddcdddcdc","ccdcc"}

    20

    Returns: 131072

  15. 18

    {"ddcdcdcdcdddccd","ccdccdcdcddcdd","cdcdccccdcd","cdcdddcddcdcd","dddddcdccdcdd","ccdcccccddc","cdc","cccccdcdccddcddcc","dcc"}

    27

    Returns: 262144

  16. 17

    {"ddddccccddccdccd","dcdcdcdddddcddd"}

    26

    Returns: 131072

  17. 17

    {"cddddcd","ddccddddcdd","cddcdcddddc","ddccdccccddcddccc","d","dddddccdcdcdcddddd","ccd","dcddccdccdcdddccd","dcddccdcccdddcc","dcccdcccdd"}

    3

    Returns: 22

  18. 18

    {"dcddc","dccdccdcc","ccccd","cccdcdcc","dddccccdddd","cdc","dccdcdcddc"}

    29

    Returns: 262144

  19. 16

    {"cdcdcdcddddcddddcd","dddd","dcdccccddc","cdccccd","dcd","c","dcccddcccdcddc","ccd","dcdcddcccddccdcd","cddddcdd"}

    16

    Returns: 63679

  20. 18

    {"ddcccdc","ccddccdcdcc","dccccdddcdcccccdc"}

    2

    Returns: 261898

  21. 15

    {"dcdcccc","dccccccc","ccddcdcccdcddd","dcc","ccccdd"}

    9

    Returns: 32768

  22. 17

    {"dcdccd","ccdcd","ccd","dcdccddddd"}

    9

    Returns: 131072

  23. 18

    {"dcc","ddcddcdcdcccdddccd","ccccddd","cccddccdcdccc","dddccdccdcdc","dddddddcddccdddd","dcdcdcdc","ccccdd"}

    3

    Returns: 149897

  24. 14

    {"dccccddcccdc","cd","cddcddd","dccdcdccccc","ddccd","cccdccccdc","dddddccd","ddcccdd"}

    5

    Returns: 12273

  25. 14

    {}

    22

    Returns: 16384

  26. 15

    {}

    24

    Returns: 32768

  27. 18

    {"dccccccc","dcdcccddcdcdddcc","cdddccccd","dddccddd","cdddccdcccdddddddc","dddccddcc"}

    2

    Returns: 261212

  28. 17

    {"dd","c","ddcddcccccddcdd","ddddccdcc","dddccccd","ccddcddccddccccdc","cdddddcccdcccdcccc","ddcccdddccc"}

    22

    Returns: 131072

  29. 14

    {"dddddccc","ccd","ccccddcdccdccd","dcdcddccccdcccdc","dddccc","cdddddcd","c","dcdccdcccdcddc","ccdddcdddcdccd","d"}

    13

    Returns: 0

  30. 14

    {"ddddcddddccdddd","ddcddd"}

    18

    Returns: 16384

  31. 17

    {"cddccdddcddcccdddc","cdddcd","cdccc"}

    23

    Returns: 131072

  32. 18

    {"d","cdcdccdcdcdddcdddc","dddcc","dcdddccc","cdddddddcccd","ddd","ddcddccdcdc","ddcc","dcd"}

    4

    Returns: 563

  33. 14

    {"ccddddccc","cdc","dccdcdcc","d","dccccccddcdcd","dcddddc"}

    29

    Returns: 16384

  34. 17

    {"cdddccccddddc","cccccccccddccddd","dcdccdccccdcccd","ccddcddcdccccc","cccdccdcccddddd","ddcddccccddddcddd","d","dccdcdcdddcdcd","dddddddccd","ccdcdddcccddddcd"}

    3

    Returns: 154

  35. 14

    {"c","dddcc","cc","dddcdddcddddcccccd","dcddddcdccdddccdcd","cddcddddccccdcddcc","ccccdcd","dd"}

    17

    Returns: 13551

  36. 18

    {}

    25

    Returns: 262144

  37. 15

    {}

    3

    Returns: 32768

  38. 17

    {"cccc","d","cdcdcdddcddd","dccdccccccccc"}

    9

    Returns: 39828

  39. 16

    {"dcdddd","cdcdddcdcddcdccdc","ddddcccc","cdddcccddc","ddcddddcdcccdddcd","cdcd","ddcddcdddddcddddc","cddcdd","cddcc","ddccd"}

    27

    Returns: 65536

  40. 14

    {"dd","ccccdccdcdcccccccd","dcddddcdcd","dddddcddcdccdcd","ccccdccddcdcd","ddcdd","dccdcdccccdcddcc","dcccd","dccdcddccdcddcddc"}

    3

    Returns: 4936

  41. 15

    {}

    18

    Returns: 32768

  42. 18

    {"ccc","dcdd","dccccd","ccccdddccdddcdd","ddccddcccddcdcccdc","ddddccddddd","cdd","dcddccdddccccd"}

    22

    Returns: 262144

  43. 15

    {"ddcdcddcc","dccdcdcdccccdccccd","dc","ccccddcdddcdcddd","d","cdcddcdccdcc","cccccddcdddd","ddcdcc","dddcd","cccdc"}

    7

    Returns: 569

  44. 18

    {"ddc"}

    7

    Returns: 262144

  45. 16

    {}

    13

    Returns: 65536

  46. 17

    {"cdddc","ddcdddcdcddcdcddcc","dcd","dddcdcccdcccddc"}

    8

    Returns: 131051

  47. 17

    {"ccddd","ddccdddcdd","d"}

    30

    Returns: 131072

  48. 16

    {"dddddcccddd","d","cddcddccdc"}

    15

    Returns: 65519

  49. 15

    {"dccdcdccdccccdc","cdcdccdd","dddcc","cdcdddcdddcddc","dcddc","cccccdcddcc","ddcddd","ddcdddcdcdddccdd","ddccccdddc"}

    15

    Returns: 32768

  50. 16

    {"ddd","cddddcdc","dcddcdcddcdddd","dcdccdcdccdc","dddccddcdddddddcdd","cdddddccdcdcdccccd","ccdddcdd","dccdcddc"}

    5

    Returns: 59703

  51. 17

    {"dccdddcdd","c","ddccdddcdcdcccc","ddcdcdcdddddd"}

    11

    Returns: 109219

  52. 18

    {"ddccddddcdd","dccd","dd","ddddddcdddcccdcd","cddcddcccdcddcdcd","dcdddcdc","cccddcddcccd","dddcd","ddd","ccccddcdd"}

    27

    Returns: 262075

  53. 16

    {"ddcddddcccddcdccd","cdc","cccc","ddcddcdddddccdddc","ccdcdddccdc"}

    17

    Returns: 65536

  54. 16

    {"ccccddcccddccc","cdccdddcccdddc","dcdddd","dcccdddcdcd","ccccdcddd","ddddddccccccc"}

    9

    Returns: 65536

  55. 18

    {"ddddc","cddccddcdddcc","cddcccccddddcddccd","dcdcddd"}

    5

    Returns: 262144

  56. 18

    {"ccdccc","dddccdddcdcdcc","dccccdccc","ddddc","dddcccccdcd","cdddddcdccdc","dccccdcdccddddcdd","cccdc","dcddcdc","dcdc"}

    6

    Returns: 259998

  57. 16

    {"ddcdccdccdcdc","d","cdcdccccccdcddc","dcdcdcdcc","dddccdc"}

    11

    Returns: 57746

  58. 14

    {"cccddc","cddddccc","ddcccddccdc","cdcdddddddddc","d","cccdcdddcddc","dccdddcdcc","dc","ccdccddcddcccd","ccccdcdccdddccc"}

    15

    Returns: 16383

  59. 14

    {"cccdcdccddddcdd","dccddcccdcddddcdd","cdcddddccccc","cc"}

    26

    Returns: 16384

  60. 16

    {"dcdc","d","ddcccdccd","dcddccdcc","cdcdddcddc","dddddddccddccdcc"}

    19

    Returns: 65536

  61. 16

    {"ddcdc","dccdcdddccc","ddcddcddccdcdcc","dcdcdcdcccddddcdcc","ccc","cc","dc","cddcccdcddccdcccdc"}

    8

    Returns: 18617

  62. 15

    {"dccddcc","dccccdcccdc","dddcdcc","cddcdcccdccccdcdc","ccdcdddcddcdcdddcd","c","cdcdcc"}

    7

    Returns: 8866

  63. 16

    {"cddcdddddccccdd","dddccdcdddcddc","ccc","cc","dcdddcdcdcdccddc","dccccc","d","dcccccddc"}

    22

    Returns: 64797

  64. 16

    {"dccccc","cdcd","dddc","ddccc","dddccddcdd"}

    29

    Returns: 65536

  65. 18

    {"ccdccdcddcddcccc","ccdcdcdc","cccccccdccddcccc","cdcddcccd"}

    5

    Returns: 262144

  66. 15

    {"ccdccdccd","cdd","ccccccdcd","dd"}

    11

    Returns: 32209

  67. 15

    {"cc"}

    28

    Returns: 32768

  68. 16

    {"cdccdccdddccddddcd","dddcdcdccc","d","ccdd","ddddcdddcdc","dcccdcdddcdcdddc","dccdccddccdccdccdd","dddccdd","cdddddddcdcdc"}

    2

    Returns: 17

  69. 14

    {"ddccddccdccdcd","cdccdccdddddcdc","dccddcccdccdcd","dcdccdcdd","cdccddddcdcc","dcdddc"}

    22

    Returns: 16384

  70. 17

    {"cdc","ddcccccdd"}

    4

    Returns: 116941

  71. 16

    {}

    17

    Returns: 65536

  72. 18

    {"dcdddcdc","ddddccccdddcccdddc","cddddcccdcddcdd","cdccccdcccdcdccdd","cccddccdddcccc","ccccdddcdddcccddcd","ccddc"}

    9

    Returns: 262144

  73. 14

    {"dddddd","dddccdddddc"}

    29

    Returns: 16384

  74. 16

    {"cdddcd","d","ddddcddcddccdcddd","ccdcc","ddddddcdcddddcc","dddddddd"}

    4

    Returns: 232

  75. 17

    {"cddcdccddccddddcdd","ccdcddcd","dddddddcccccdcdcd","ddcc"}

    11

    Returns: 131072

  76. 15

    {"ccdc","dcc","ddccddcdcdcdcccdd","d","ddccdccdcccc","dc","ccdccddddcccddd","cdcddcddcc"}

    29

    Returns: 32768

  77. 14

    {"cdccdcdccdddcdccc","dcdddddccccdcdccc","ccdcdcddccdddddc","cdc","dccddcdcdcccd","dddccdddcc"}

    28

    Returns: 16384

  78. 14

    {}

    21

    Returns: 16384

  79. 14

    {"dd","cdddc","dcdccccccddc","ccdcddcc","dddd","cddccccddc","dccccdcdcdcddccd","dcccdcdddcdcddcdd"}

    5

    Returns: 9899

  80. 14

    {"ddcdccddd","cddcd","cddddccddcdddddc","ccccdccd"}

    11

    Returns: 16384

  81. 15

    {"ccdddcdd","ddddcccdcd","cccdcddcdcccc","cdddddcddddccdcccd","c","cddccddddddddc","dcc","cdddccdccccc"}

    16

    Returns: 32768

  82. 14

    {"dddcdd","dcccddddddddcccc","ddcdcdccdcdddcddc","dccddcdccd"}

    4

    Returns: 16384

  83. 15

    {"cccdccdddcd","dcdccd"}

    1

    Returns: 27732

  84. 14

    {"dcddddddcddcddd","dcdddcdcdd"}

    30

    Returns: 16384

  85. 14

    {"cdcc","cd","cdddcddcdccdddccc"}

    6

    Returns: 14295

  86. 5

    {"ccddccccdddddcccdd","ddcddd","cddccccdcdddcd","ccccc"}

    4

    Returns: 32

  87. 2

    {"cdccdd"}

    26

    Returns: 4

  88. 4

    {"dcccc","dc","cccc","dcccddddcdd","c","cddcdcccdcdcddcd","ddcdc"}

    19

    Returns: 16

  89. 7

    {"cddcdcddcddcdccc","dcdcdc","dcddccdddcd","cdcccdccddcc","dcdcddddcccc","c","dddccdccddcddd","dc"}

    7

    Returns: 105

  90. 6

    {"cccddddcddcdddd","cccccdcd","cdcdcc","cddcdcdcdcccd","dd","cddcdcddddcdd","cddcd","cdccdccddc","ccddcc"}

    7

    Returns: 64

  91. 4

    {"ccc","dcddccccdddccdcd","dddccddcccccdc","cdcccdcdcccdccc","dccdcdcdcccc","dddcddcdddc","cdccccccccddcccccc","dd","cccdcdc"}

    20

    Returns: 16

  92. 6

    {"cd","dddd","dc","ddcdcdcccdcdccddd"}

    24

    Returns: 64

  93. 2

    {"cc","cddc","cccc","dddd","dcd"}

    1

    Returns: 3

  94. 2

    {"ccccdccccccdddc","c","cccd","dddddddcc","dc","ccdcddddccdcdddcd"}

    20

    Returns: 4

  95. 6

    {"ccdcdddcddddcddddc","d","dddcddd"}

    26

    Returns: 64

  96. 1

    {"dddcddcdddc","ddccccdcdccccddc","ccddcdc","dddcddcdcccdcccdd"}

    2

    Returns: 2

  97. 5

    {"ddddccdddccc","ccdcdddccdcddcdcdc","cdcccc","cddddcdccdccdccdc","ddcdcdcdc"}

    25

    Returns: 32

  98. 5

    {"dcccddddddcdccdc","c","dddccdddc","cdddcccdcdcccccccd","cdc","dcdccddddcddddc"}

    29

    Returns: 32

  99. 7

    {"cddc","ddddccdcccdccdccc","cdddddddcccd","c","dcdccdcccccc","cddcccc","cddccdccdcc","ccdcdccccc"}

    9

    Returns: 128

  100. 7

    {"ccddc","cccccc","cccdcdcdccdcdc","ccddcccdcdc","ccccccdc","cdddcddcdddcccccdd","ddcccddd","dd"}

    11

    Returns: 128

  101. 7

    {"cdddddccdcdcddc","ddddcddccdcc","dddcccdcc","dddcdc","c","cdccdc"}

    30

    Returns: 128

  102. 1

    {"ddddcccdcdcd","d","dddccdddcdddcccdcd","cdcdc","ccddcdcdd","cddddcddcddcd","ccdccdcddcc","cdcccccdddddcccd"}

    3

    Returns: 2

  103. 5

    {}

    6

    Returns: 32

  104. 1

    {"cdcccccdddddccdcc"}

    7

    Returns: 2

  105. 7

    {"cddddccdd","cdddcdd","ccc","ccccdccccdcdddc"}

    5

    Returns: 127

  106. 18

    {"c","d","cd","dc","cc","dd","cdd","ccc","ddc","dcc"}

    100

    Returns: 262144

  107. 18

    {"ccccc","ccccd","cccdc","cccdd","ccdcc","ccdcd","ccddc","ccddd","cdccc","cdccd"}

    100

    Returns: 262144

  108. 18

    { "c", "cc", "ccc", "cccc", "ccccc", "cccccc", "ccccccc", "cccccccc", "ccccccccc", "cccccccccc" }

    100

    Returns: 262122

  109. 18

    { "cdcd", "ddddc", "ccdcdc", "cdc" }

    4

    Returns: 146712

  110. 18

    { "cccccccccccccccccc", "cccccccccccccccccd", "ccccccccccccccccdc", "cccccccccccccccdcc", "ccccccccccccccdccc", "cccccccccccccdcccc", "ccccccccccccdccccc", "dddddddddddddddddc", "ddddddddddddddddcd", "dddddddcdddddddddd" }

    100

    Returns: 262144

  111. 18

    { "cccccccccccccccccc", "dddddddddddddddddd", "ccddccddccddccddcc", "ddccddcccccccccccc", "ddddddcccddddddddd", "cccccccccccccccccd", "dddddddddddddddddc", "cccddccdddddddcccc", "cccdddddddddcccccc", "cccccccccccdddddcc" }

    100

    Returns: 262144

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: