Solution for a Probability Game-Theory Problem — UVa 1413

Revision en3, by dbedi3311, 2021-12-15 01:30:32

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.

Tags icpc, probability, math, competitive programming, coding

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English dbedi3311 2021-12-15 01:30:32 2
en2 English dbedi3311 2021-12-15 01:29:42 64 (published)
en1 English dbedi3311 2021-12-15 01:28:09 1381 Initial revision (saved to drafts)