Contest in running and you are posting the 550 points problem? Its unfair. Ask after it gets over.
On 6 July 2010 17:30, crazysaikat <[email protected]> wrote: > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Thanks & Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science & Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
