I came across this problem in UVa OJ called 1413-Game (UVa-1413 Game). The problem statement is essentially as follows: A group of contestants sits at a round table and they pass around a token to an adjacent person (either to their left or right) with a certain probability. The person who receives the token does the same with his/her probability and so on. The game stops once each person has received the token at least once, and the last person with the token wins.

Given input the number of contestants, n (0 <= n <= 50), and the number of the contestant who starts with the token, k (k < n) as well as a list of probabilities p_i that contest i passes the token to the right, determine the probability that contestant n wins the game. Your output should be accurate to 6 digits after the decimal.

I want to improve my probability implementation skills, especially since I think it will be relevant for ICPC. Let me know of any solutions (preferably with code-attached) I can view.

As a side note: this problem was taken from Art of Algorithms for Programming Contests Training Guide by Ruijia Liu. If anyone has access to a pdf, preferably in English, of the book and wouldn't mind sending it over, that would be much appreciated.

Past USACO Problems

In terms of preparation in solving USACO gold problems, (currently when there are 4 divisions, plat, gold, silver, and bronze) how would silver/gold problems (when there were only 3 divisions) be comparable to current gold division problems? In specific, would the previous silver division or gold division have problems of the same difficulty as current gold? Would past years silver problems be more beneficial to solve, or would previous years' gold problems be more ideal to prepare for the current USACO gold?

Dynamic Programming and Contest Prep

Also as a side note, could someone provide links/resources to learn dynamic programming (dp) because that is my weak point. I understand the nature of dynamic programming problems, however, I often struggle to come up with a solution that builds off the optimal substructure. Additionally, what else would one recommend to perform well in USACO gold contests, apart from learning algorithms and practicing previous USACO problems?

Thanks for all the help!