Thought Process

Build a decision tree and see what happens. There are 3 options:

1. We picked 2 red cards:

   • This had a X = R(R-1) / ((R + B)(R + B - 1)) chance of happening

   • In this case they are both discarded, so we move to the case P(R - 2, B)

2. We picked 1 red card and 1 black card (in either order):

   • This had a Y = 2*R*B / ((R + B)(R + B - 1)) chance of happening

   • In this case we discard the black card, so we move to the case P(R, B - 1)

3. We picked 2 black cards:

   • This had a Z = B(B - 1) / ((R + B)(R + B - 1)) of happening

   • In this case both cards are put back in, so we are back to the starting case of P(R, B)

This means that we have P(R, B) = X * P(R - 2, B) + Y * P(R, B - 1) + Z * P(R, B), we solve for P(R, B) to get P(R, B) = (X * P(R - 2, B) + Y * P(R, B - 1)) / (1 - Z).

This means we can solve the problem with recursion/dynamic programming. I went for dynamic programming since the recursion stack grew too large. 

Generate a R x B matrix with the initial conditions:

1. P(0, B) = 1 for all B greater than or equal to 0

2. P(R, 0) = 0 for all R greater than or equal to 1

Now simply fill in the array in O(RB) time! 

Speedup: We can speed this up by a factor of 2 by noticing that R must be even (I'll let you figure out why)