Statistics

Problem Statement for "RabbitStepping"

Problem Statement

Rabbits often feel lonely, so one group of rabbits decided to gather together and play a game.

The game is played on a horizontal row of N cells (N >= 2), numbered 0 to N - 1 from left to right. Each cell is colored white, black or red. You are given a String field of length N, where the i-th character is the color of cell i ('W' for white, 'B' for black and 'R' for red).

There are r rabbits playing the game. The rabbits choose their starting cells randomly such that no two rabbits are on the same cell. Each subset of r distinct cells has the same probability of being chosen as their starting cells. The size of the field is the number of cells it contains (which is initially N). The following is repeated while the size of the field is greater than 2:

  • Each rabbit steps onto a neighboring cell. Since each cell potentially has up to two neighboring cells, the following rules are used to determine which cell the rabbit will choose:
    • If a rabbit is on cell 0, she must step onto cell 1.
    • If a rabbit is on cell size - 1 or size - 2, she must step onto the left neighboring cell.
    • All other rabbits choose which neighboring cell to step onto according to the color of the cell they are currently on:
      • White: She must step onto the left neighboring cell.
      • Black: She must step onto the right neighboring cell.
      • Red: If this is her first move, she must step onto the left neighboring cell. Otherwise, she must return to the cell she was on immediately before she was on the current cell.
  • After all rabbits finished their steps, for each cell that contains more than one rabbit, all rabbits on that cell will be removed from the field.
  • The rightmost cell will disappear (causing the size of the field to decrease by 1). By the rules above, this cell will always be empty.
When the game ends, 0, 1 or 2 rabbits will remain on the field. Return the expected number of rabbits left on the field when the game ends.

Definition

Class:
RabbitStepping
Method:
getExpected
Parameters:
String, int
Returns:
double
Method signature:
double getExpected(String field, int r)
(be sure your method is public)

Notes

  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • field will contain between 2 and 17 characters, inclusive.
  • Each character in field will be either 'W', 'B', or 'R'.
  • r will be between 1 and N, inclusive, where N is the number of characters in field.

Examples

  1. "WRBRW"

    4

    Returns: 0.8

    The initial positions of the rabbits are cells { 0, 1, 2, 3 }, { 0, 1, 2, 4 }, { 0, 1, 3, 4 }, { 0, 2, 3, 4 }, or { 1, 2, 3, 4 }. For example, if { 0, 1, 2, 4 } is chosen, they will step as follows and 2 rabbits will remain on the field:

  2. "WWB"

    2

    Returns: 1.3333333333333333

  3. "WW"

    1

    Returns: 1.0

    No moves will be performed, and one rabbit will remain alone on the field.

  4. "BBBBBBBBBB"

    4

    Returns: 0.9523809523809523

  5. "RRBRRWRRBRRW"

    8

    Returns: 0.9696969696969697

  6. "WB"

    1

    Returns: 1.0

  7. "BW"

    2

    Returns: 2.0

  8. "RBR"

    1

    Returns: 1.0

  9. "BBB"

    2

    Returns: 1.3333333333333333

  10. "BBB"

    3

    Returns: 1.0

  11. "WWBR"

    1

    Returns: 1.0

  12. "WWRR"

    2

    Returns: 1.3333333333333333

  13. "RBRR"

    3

    Returns: 1.0

  14. "RBRW"

    4

    Returns: 0.0

  15. "RBBWB"

    1

    Returns: 1.0

  16. "RWWWW"

    2

    Returns: 1.2

  17. "RBRBW"

    3

    Returns: 1.0

  18. "WWWWB"

    4

    Returns: 0.8

  19. "RBWRW"

    5

    Returns: 1.0

  20. "WBRBRR"

    1

    Returns: 1.0

  21. "WBBWBW"

    2

    Returns: 1.2

  22. "RBRRBB"

    3

    Returns: 1.0

  23. "BBWWWB"

    4

    Returns: 0.8

  24. "WRRWRW"

    5

    Returns: 1.0

  25. "WRRRBW"

    6

    Returns: 2.0

  26. "WWWWWWWWWWWRRRRR"

    1

    Returns: 1.0

  27. "RRRRRRRRRRRRRRRR"

    2

    Returns: 1.0666666666666667

  28. "BBBBBBBBRRRRRRRR"

    3

    Returns: 1.0

  29. "WWWWWWWWWWWWBBBB"

    4

    Returns: 0.9846153846153847

  30. "BBWWWWWWWWWWWWWW"

    5

    Returns: 1.0

  31. "WWWWWWWWWWWWWWWW"

    6

    Returns: 1.006993006993007

  32. "BBBBBBBBBBBBBBBB"

    7

    Returns: 1.0

  33. "RRRRRRRRRRRRRRRR"

    8

    Returns: 0.9945609945609946

  34. "BBBBBBBBBBBBBRRR"

    9

    Returns: 1.0

  35. "BBBBBBBBBBBBBBBB"

    10

    Returns: 1.006993006993007

  36. "RRRRRRRRRRRRRRRR"

    11

    Returns: 1.0

  37. "WWWWWWWWWWWWBBBB"

    12

    Returns: 0.9846153846153847

  38. "BBBBBBBBBRRRRRRR"

    13

    Returns: 1.0

  39. "RRRRRRRRRRRRWWWW"

    14

    Returns: 1.0666666666666667

  40. "BBBBBBWWWWWWWWWW"

    15

    Returns: 1.0

  41. "RRRRWWWWWWWWWWWW"

    16

    Returns: 0.0

  42. "BBBBBBBBBBBBBBBBB"

    1

    Returns: 1.0

  43. "WWWWWWWWWWBBBBBBB"

    2

    Returns: 1.0588235294117647

  44. "BBBBBBBBBBBBBBBBB"

    3

    Returns: 1.0

  45. "BBBBBBBBBBBBBBBBB"

    4

    Returns: 0.9882352941176471

  46. "BBBBBBBBBBBBRRRRR"

    5

    Returns: 1.0

  47. "WWWWWWWWWWWWWWWWW"

    6

    Returns: 1.004524886877828

  48. "RRRRRRRRRRRRRRRRR"

    7

    Returns: 1.0

  49. "RRRRRRRBBBBBBBBBB"

    8

    Returns: 0.9971205265322912

  50. "BBBBBBBBBBBRRRRRR"

    9

    Returns: 1.0

  51. "WWWWWWWWWWWWWWWWW"

    10

    Returns: 1.0028794734677087

  52. "RRRRRRBBBBBBBBBBB"

    11

    Returns: 1.0

  53. "BBBBBBBBBBBBBBBBB"

    12

    Returns: 0.995475113122172

  54. "RRBBBBBBBBBBBBBBB"

    13

    Returns: 1.0

  55. "RRRRRRRRRRRWWWWWW"

    14

    Returns: 1.011764705882353

  56. "RRRRRRRRRRRRRRRRR"

    15

    Returns: 1.0

  57. "BBBBRRRRRRRRRRRRR"

    16

    Returns: 0.9411764705882353

  58. "WWWWWWWWWWWWWWWWW"

    17

    Returns: 1.0

  59. "RWRR"

    3

    Returns: 1.0

  60. "RRBWB"

    2

    Returns: 1.2

  61. "BBBWRRBWWWB"

    8

    Returns: 0.9696969696969697

  62. "RBWRWWR"

    7

    Returns: 1.0

  63. "BBB"

    1

    Returns: 1.0

  64. "RBR"

    2

    Returns: 1.3333333333333333

  65. "RBWWW"

    5

    Returns: 1.0

  66. "WBR"

    2

    Returns: 1.3333333333333333

  67. "WWBBR"

    3

    Returns: 1.0

  68. "BWBRRWBRBW"

    9

    Returns: 1.0

  69. "WWWBRRW"

    5

    Returns: 1.0

  70. "RRRWW"

    1

    Returns: 1.0

  71. "RWRRRWB"

    3

    Returns: 1.0

  72. "BBRWBBWRR"

    4

    Returns: 0.9523809523809523

  73. "RW"

    2

    Returns: 2.0

  74. "RRWR"

    1

    Returns: 1.0

  75. "RWB"

    2

    Returns: 1.3333333333333333

  76. "RRRWBRWRRRW"

    1

    Returns: 1.0

  77. "BBBWRWBWBRR"

    3

    Returns: 1.0

  78. "RR"

    1

    Returns: 1.0

  79. "RWWRWBR"

    2

    Returns: 1.1428571428571428

  80. "RRRWRBBB"

    8

    Returns: 0.0

  81. "BRWRWRBWBB"

    9

    Returns: 1.0

  82. "RW"

    2

    Returns: 2.0

  83. "WRRRRRRBRWWW"

    6

    Returns: 1.0216450216450217

  84. "BRBBWB"

    5

    Returns: 1.0

  85. "BWBWWBR"

    4

    Returns: 0.9142857142857143

  86. "BRWWBWBWWR"

    1

    Returns: 1.0

  87. "WBWWBB"

    4

    Returns: 0.8

  88. "RBWBBRRRWRBW"

    10

    Returns: 1.0909090909090908

  89. "WRB"

    3

    Returns: 1.0

  90. "WWBBRRB"

    5

    Returns: 1.0

  91. "WRWB"

    3

    Returns: 1.0

  92. "WBBWRWWBWW"

    6

    Returns: 1.0476190476190477

  93. "BBBBRWBBBWB"

    10

    Returns: 1.0909090909090908

  94. "WB"

    1

    Returns: 1.0

  95. "WWBRRBWR"

    2

    Returns: 1.1428571428571428

  96. "WRWRWWR"

    3

    Returns: 1.0

  97. "RRWRWBWWBRB"

    5

    Returns: 1.0

  98. "BBRWWRWBW"

    3

    Returns: 1.0

  99. "BBBRWRBBRR"

    4

    Returns: 0.9523809523809523

  100. "BWBRWBB"

    2

    Returns: 1.1428571428571428

  101. "RRBRRRBWRRBWBWWRR"

    5

    Returns: 1.0

  102. "RRRRRRRRRRRRRRRRR"

    8

    Returns: 0.9971205265322912

  103. "WBRWBRWBRWBRWBRWB"

    16

    Returns: 0.9411764705882353

  104. "RRWBRRWRWRRBRBRBR"

    9

    Returns: 1.0

  105. "RRBRRWRRBRRWRRRRR"

    8

    Returns: 0.9971205265322912

  106. "RRBRRRWRRBRRWWW"

    10

    Returns: 1.006993006993007

  107. "RRRRRRRRRRR"

    4

    Returns: 0.9696969696969697

  108. "WWW"

    3

    Returns: 1.0

  109. "BB"

    2

    Returns: 2.0

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: