TopCoder problem "CyclicGame" used in SRM 318 (Division I Level Two)



Problem Statement

    

You are playing a one-player game where several cells are arranged around a circle, and each cell contains a value. You have a bank that is initially empty, and you start on the 0-th cell. On each turn, you throw a typical six-sided die (each side has a distinct number between 1 and 6), and you move clockwise the number of cells indicated on the die. The value in the cell that you land on will be added to the bank. The goal is maximize the value of the bank.

Unfortunately, the sum of all the values on the cells is negative, so the expected value of the bank after a long game is also negative. Therefore, you should stop the game at the proper time.

You will be given a int[] cells that contains the values of the cells in clockwise order. The 0-th element of cells is the value of the 0-th cell. Return the expected value of the bank if you play optimally. See examples for further clarification.

 

Definition

    
Class:CyclicGame
Method:estimateBank
Parameters:int[]
Returns:double
Method signature:double estimateBank(int[] cells)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-cells will contain between 2 and 15 elements, inclusive.
-Each element of cells will be between -100 and 100, inclusive.
-The sum of all elements in cells will be negative.
 

Examples

0)
    
{-10, 1, 1, 1, 1, 1, 1, 1, 1}
Returns: 1.3611111111111112

You are guaranteed get 1 point on the first turn. When you're on cell 1 or 2 (0-indexed), you can safely take another turn to get one more point, but if you're on cells 3 through 8, your best option is to stop the game.

The expected result for the bank value is 1 + 1/6*(1 + 1/6*1) + 1/6 = 1.36.

1)
    
{-10, 7, -5, 7}
Returns: 0.30434782608695654
You should stop the game if you're on cell 2 or 3.
2)
    
{-1, -2, 2}
Returns: 0.0
The expected result of any move is 1/3*(-1)+1/3*(-2)+1/3*2 = -1/3, so the best choice is not play at all.
3)
    
{-40, 9, 9, 9, 9, 9, -44, 9, 9, 9, 9, 9, -40, 15, 15}
Returns: 3.5653612433724144
You should stop the game if you're on cells 9 through 11 (where two cells with value -40 are reachable in one turn).
4)
    
{-36, 95, -77, -95, 49, -52, 42, -34, -1, 98, -20, 96, -96, 23, -52}
Returns: 12.395613307567126

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9998&pm=6216

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Brute Force, Math