TopCoder problem "RedIsGood" used in SRM 420 (Division I Level Two)



Problem Statement

    

You have a deck that contains R red and B black cards.

You are playing the following game: You shuffle the deck, and then begin dealing the cards one by one. For each red card you flip you get a dollar, and for each black card you flip you have to pay a dollar. At any moment (including the beginning of the game) you are allowed to stop and keep the money you have.

Write a method that will take the ints R and B, and return the expected amount you will gain if you play this game optimally.

 

Definition

    
Class:RedIsGood
Method:getProfit
Parameters:int, int
Returns:double
Method signature:double getProfit(int R, int B)
(be sure your method is public)
    
 

Notes

-During the game, your balance may be negative.
-We assume that each permutation of the cards in the deck is equally likely.
-Your return value must have a relative or absolute error less than 1e-9.
 

Constraints

-R will be between 0 and 5,000, inclusive.
-B will be between 0 and 5,000, inclusive.
 

Examples

0)
    
0
7
Returns: 0.0
If all cards are black, the best strategy is not to play at all.
1)
    
4
0
Returns: 4.0
If all cards are red, the best strategy is to flip them all.
2)
    
5
1
Returns: 4.166666666666667
The strategy "flip all cards" is guaranteed to earn $4. However, we can do better. If we flipped 5 cards and all of them are red, it makes no sense to flip the final, black card. Therefore if we play optimally the expected gain is more than $4.
3)
    
2
2
Returns: 0.6666666666666666
An optimal strategy for this case: Flip the first card. If it is red, stop. If it is black, flip the second and the third card. If both are red, stop, otherwise flip the fourth card.
4)
    
12
4
Returns: 8.324175824175823
This is a game I would surely like to play often.
5)
    
11
12
Returns: 1.075642825339958
Surprisingly, sometimes there is a good strategy even if the number of red cards is smaller than the number of black cards.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9915

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13511&pm=9915

Writer:

misof

Testers:

PabloGilberto , Olexiy , ivan_metelsky , zhuzeyuan

Problem categories:

Dynamic Programming, Math