Connection Status:
Competition Arena > CatsOnTheCircle

CatsOnTheCircle

SRM 667 · 2015-08-28 · by lg5293

SRM 667 · 2015-08-28 · by lg5293 · Advanced Math
Class Name: CatsOnTheCircle
Return Type: double
Method Name: getProb
Arg Types: (int, int, int)
Problem Statement

Problem Statement

There are N cats sitting around a circle. The cats are numbered 0 through N-1 in clockwise order. Note that as they sit around a circle, cat N-1 is adjacent to cat 0. The cats are playing a game and the winner will get a prize!

The game looks as follows:

  • There is a single ball. Initially, cat 0 holds the ball.
  • In each round of the game, the cat who currently holds a ball flips a biased coin. The coin will come up heads with probability p/1,000,000,000 and tails with probability 1-(p/1,000,000,000).
  • If the coin came up heads, the current cat will hand the ball to the next cat clockwise, otherwise the current cat will hand the ball to the next cat counterclockwise. Formally, if the current cat is cat j, heads means that the ball goes to cat (j+1) mod N and tails means that it goes to cat (j-1) mod N.
  • The game is played until each cat held the ball at least once. The cat who holds the ball at the end of the game is the winner.

In other words, the winner is the last cat to touch the ball. Note that cat 0 holds the ball at the beginning, and this does count as holding the ball. Hence, if there is more than one cat, cat 0 can never win the game.

Cat K wonders what is the probability that she will win the prize. You are given the ints N, K, and p. Return the probability that cat K wins.

Notes

  • Your return value must have an absolute or relative error smaller than or equal to 1e-6

Constraints

  • N will be between 3 and 1,000,000,000, inclusive.
  • K will be between 1 and N-1, inclusive.
  • p will be between 1 and 999,999,999, inclusive.
Examples
0)
3
1
300000000
Returns: 0.6999999999999985

This game has N=3 cats, labeled 0, 1, 2. We have p=30,000,000, hence the coin will come up heads with probability 30,000,000/1,000,000,000 = 0.3 and tails with probability 0.7. The game can look as follows: Cat 0 is given the ball. Cat 0 flips the coin. The coin comes up tails. Cat 0 hands the ball to cat (0-1) mod 3 = cat 2. Cat 2 flips the coin. The comes up tails again. Cat 2 hands the ball to cat (2-1) mod 3 = cat 1. At this moment, each cat has held the ball. The game ends and cat 1 gets the prize. This particular sequence of events has probability 0.7*0.7 of occuring. It can be shown that the probability that cat 1 wins the game is 0.7.

1)
6
2
500000000
Returns: 0.2

The coin that is flipped will come up heads with probability 1/2, and tails with probability 1/2.

2)
6
5
500000000
Returns: 0.2
3)
10
2
666666666
Returns: 0.00391389439551009
4)
999999999
999999996
777777777
Returns: 0.05830903870125612

Submissions are judged against all 62 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CatsOnTheCircle with a public method double getProb(int N, int K, int p) · 62 test cases · 2 s / 256 MB per case

Submitting as anonymous