AVMG1 - Another Valentine Maze Game (1D)

no tags 

Happy Valentine Day!

Valentine Maze

Picture Source: http://www.printactivities.com/Mazes/Shape_Mazes/Heart_Maze.html

In this valentine day, I'm very happy to know that many SPOJ user happy to help me on my old Valentine Maze Game (2 years ago). I can't imagine what happen if no one guide me in the maze to meet her (my love), of course it will be much worse, because I can lost in the maze for long time. Now, can you help me again to compute what is expected time needed to meet her in the maze if I just walk uniform randomly on all possible dirrection without any guide? I will be very grateful for your help.

For simplicity, in this problem there will be no Chocolate, Wall, and the Maze will be 1 Dimension only.

Given a map length l, containing 3 possible elements:

'.' denoting road (I can walk on this area)

'T' denoting my position (Tjandra) at start (time 0), only appear once on the map.

'W' denoting Woman I want to meet (Destination), only appear once on the map.

Tjandra always walk one step left or right (if valid, valid = I still inside the maze) for each unit of time with equal probability, I never stop until I arrive on my destination. 


On the first line, there is an integer t denoting number of test cases. Number of test case will be less than or equal to 250.

For each test case there are two lines, the first one there is an integer l denoting length of map. Length of map will be less than or equal 50. Next line there are l characters, each character is element of map that has been described above.


For each test case, output expected time required for me to meet her if I just walk uniform randomly on all possible dirrection. Your answer are considered correct if absolute error with judge (my) solution is less than 10-5. It's guaranteed that my solution has absolute difference less than 10-19 with exact answer.





On first test case at time 0, I have one choice: walk right, at time 1 the map will be ".TW" I have two choice , walk right or left with equal probability 0.5 vs 0.5. If I walk right then my mission is completed, so there are 0.5 (50%) chance that I completed my mission at time 2. If I walk left, at time 2 the map will be back to first "T.W" I have one choice again (walk right), at time 3 the map will be ".TW" I have two choice again with equal probability. If I walk right then my mission is completed, so there are 0.5*0.5=0.25 (25%) chance that I completed my mission at time 4. By continuing, we get the series:

2 step with (1/2) chance

4 step with (1/4) chance

6 step with (1/8) chance


the answer (expected time) will be 2*1/2+4*1/4+6*1/8+8*1/16+... this series will converge to 4.


On second test case, initial map is equal to first case at time 1, so the expected time will be 1 unit less than first case. The expected time = 4 - 1 = 3.


See also: Another problem added by Tjandra Satria Gunawan

hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2016-09-18 07:49:52

@Harsh Rumalwala<hr1212>: Let's talk about general basic statistic lesson.
If I can move from point A to point D via point C with probability 1/8
or I can move from point A to point D via point B with probability 1/16
If that two option are the only option and independent I can say my probability from point A to point D is 1/8+1/16=3/16. But of course this problem is more complex than that.
I can't explain case 3 for now because it will be long (many path to reach goal), and many people can solve this problem without me explaining case 3, I build case 3 as "confirmation" case (solvers can test his/her program against case 3 before submitting his/her code).

Harsh Rumalwala: 2016-09-18 02:47:09

@Tjandra : What if there is more than one probability to reach target with specific number of steps x like in test case 3. As the target can be reached with 4 steps by probability (1/8) or (1/16). Can you please explain how answer is 8.000000 .

Shashank Srivastava: 2015-12-15 15:14:33

Awesome Problem :D My 100th

Last edit: 2015-12-15 15:20:01
darryl: 2015-10-02 19:09:46

Haha, floating point is not even needed....

(Tjandra Satria Gunawan)(曾毅昆): 2015-02-15 19:28:25

Changed allowed precission error to 10-5. Now Teddy Budiono Hermawan get accepted with precission error about 0.00000855929999943327, although there are some nice math here so precission error can be less than 10-9 :p

Last edit: 2015-02-15 22:23:53

Added by:Tjandra Satria Gunawan
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Own Problem