Collect

TCO08 Round 4 · 2008-01-21 · by lars2520

TCO08 Round 4 · 2008-01-21 · by lars2520 · Dynamic Programming

Show categories

Class Name: Collect

Return Type: double

Method Name: expected

Arg Types: (int, int)

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?

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

1
1
Returns: 3.5

Rolling 1 die once gives an expected value of 3.5.

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
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.

1
1
Returns: 3.5

1
2
Returns: 4.249999999999999

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

Coding Area

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