TopCoder problem "CrazyRunning" used in SRM 313 (Division I Level Two)

Problem Statement


John is locked in a mansion that is shaped like a star, with a number of corridors of distinct length that meet at a common point in the center. He is desperately looking for an exit, so he wants to check the end of every corridor to see if he can find one.

He is initially at the outer end of one of the corridors. In his desperation, he does not develop a good strategy, and instead, decides to do the following: He will run to the center, and when he gets there, he will randomly enter a different corridor than the one he came from. He will then run to the outer end of that corridor, turn back, and return to the center, where he will again randomly enter a different corridor than the one he just came from (but possibly a corridor he was in before that). He will repeat this process until he has visited the outer ends of all the corridors at least once. When he reaches the end of the final corridor, he will not run back to the center again.

You will be given a int[] corridors containing the lengths of all the corridors in meters. John starts in the corridor at index 0 and will run following the described strategy until he visits the ends of all the corridors at least once. Return the expected length of John's path.



Method signature:double expectedTime(int[] corridors)
(be sure your method is public)


-John will not stop running until he has visited every corridor end.
-The returned value must be accurate to within a relative or absolute value of 1E-9.


-corridors will contain between 2 and 50 elements, inclusive.
-Each element of corridors will be between 1 and 1000000 (106), inclusive.


Returns: 30.0
He starts at the end of corridor 0 at time 0. At time 10 he is in the center, and his only option (since he never goes back to the same corridor he just came from) is to go to corridor 1. He reaches the end of corridor 1 at time 30.
Returns: 900.0
He will start from corridor 0, get to the center at time 150, enter one of the other two corridors, run to the end and back to the center at time 450. From that moment on, he has 1/2 probability to finish in 150 seconds and 1/2 to do a useless run for 300 seconds and be in the same position again. So the answer is 450 + 1/2*150 + 1/2*1/2*450 + ... + ((1/2)n*((n-1)*300+150)) + ..., which is equal to 900.
Returns: 875.0
Returns: 33550.32857142857

Problem url:

Problem stats url:




PabloGilberto , brett1479 , legakis , Olexiy

Problem categories:

Math, Simulation