TopCoder problem "Collect" used in TCO08 Round 4 (Division I Level Three)



Problem Statement

    A die has 6 sides, numbered 1-6, and each side is equally likely to come up after a roll. In this problem, you are to consider rolling N dice in K rounds. In each round, you select a subset of the dice rolled in the previous round (you have to roll them all in the first round) and reroll that subset (note that a subset can be all the dice from the previous round). After K rounds, you pick a number between 1 and 6 inclusive and multiply it by the number of dice showing that number. Your goal is to maximize this value.



Assuming optimal play, what is the maximum expected score for a given N and K?
 

Definition

    
Class:Collect
Method:expected
Parameters:int, int
Returns:double
Method signature:double expected(int N, int K)
(be sure your method is public)
    
 

Notes

-If you elect not to reroll a die in one round, you may not reroll it in any subsequent round.
 

Constraints

-N will be between 1 and 10, inclusive.
-K will be between 1 and 100, inclusive.
 

Examples

0)
    
1
1
Returns: 3.5
Rolling 1 die once gives an expected value of 3.5.
1)
    
1
2
Returns: 4.249999999999999
If you can roll twice, you should keep a 4, 5, or 6 on the first round, and reroll a 1, 2, or 3. Thus, half the time you'll reroll and expect 3.5, while the other half the time you'll expect to get a 5 (the average of 4, 5 and 6). Thus, the overall expected value is (3.5+5)/2 = 4.25
2)
    
2
2
Returns: 6.262345679012343
On the first roll, lock both if you have two threes or better. Otherwise keep the higher of the two dice if it is over 3. Otherwise, reroll both.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12014&pm=8616

Writer:

lars2520

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming