Hey anyone doing topcoder srm 375, please help me out in medium
question, question is..
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.
Samples :
"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:
1)
"WWB"
2
Returns: 1.3333333333333333
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
