TopCoder problem "PickGuitars" used in SRM 366 (Division II Level Three)



Problem Statement

    

You have been invited to a TV game show where you will play against another contestant to win free guitars. At the start of the game, there are n guitar cases arranged in a circle, each of which contains a single guitar. You make the first move by choosing one guitar and removing it from its case. The other player then chooses a guitar and removes it from its case. At this point, there might be one or two groups, where a group is defined as a maximal contiguous set of non-empty cases. You continue to take turns choosing guitars, and on each turn, the current player chooses exactly one guitar from each group. The game ends when all the guitars have been chosen.



Each player gets to keep all the guitars that he chooses during the game. Your goal is to maximize the total value of the guitars you choose. The guitars in the circle are numbered 0 to n-1 in clockwise order (guitar 0 is next to guitar n-1). You are given a int[] guitarValues, the i-th element of which is the value of guitar i. Return the maximum possible total value you can get, assuming your opponent plays a perfect strategy.

 

Definition

    
Class:PickGuitars
Method:maxValue
Parameters:int[]
Returns:int
Method signature:int maxValue(int[] guitarValues)
(be sure your method is public)
    
 

Constraints

-guitarValues will contain between 2 and 50 elements, inclusive.
-Each element of guitarValues will be between 1 and 10000, inclusive.
 

Examples

0)
    
{1,5,3,4,5}
Returns: 10
You first choose guitar 4 (which has a value of 5). Your opponent chooses guitar 1 (which also has a value of 5). There are now two groups of guitars - one group contains guitar 0 and the other group contains guitars 2 and 3. You must choose one guitar from each group, so you choose guitar 0 from the first group (which has value 1) and guitar 3 from the second group (which has value 4). Your opponent will then choose the last remaining guitar, and the game is over.
1)
    
{4,8,4}
Returns: 12
Take guitar 1 (which has value 8). Your opponent will choose one of the remaining guitars (both of which have a value of 4), and you will get the other.
2)
    
{2,1,4,1,2,1,8,1}
Returns: 12
Choose guitar 6 (which has value 8). Your opponent will choose guitar 2 (which has value 4). There are now two groups of guitars. You choose guitars 0 and 4 (both of which have a value of 2). There are now four groups, each containing one guitar, so your opponent will take all the remaining guitars.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10781&pm=8177

Writer:

jthread

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Recursion, Search