TopCoder problem "Necklaces" used in SRM 247 (Division I Level Three)



Problem Statement

    A group of n thieves needs some software to help them divide up their loot. A necklace must be divided up as evenly as possible among the gang members. The necklace is a circle of gems of different values.

The requirement is that the necklace be divided into n segments by cutting the necklace in n places. Every segment must contain at least one gem. The "inequity" of the division is the value of the most-valuable segment minus the value of the least-valuable segment. (The value of a segment is the sum of the values of the gems in that segment.) We want to minimize the inequity.

Create a class Necklaces that contains a method inequity that is given as input n and a int[] gems (the values of each gem in the necklace in order). The gems are in a circle, so the last element of gems is connected to the first element. The method should find the best way to divide the necklace and return the minimum possible inequity.

 

Definition

    
Class:Necklaces
Method:inequity
Parameters:int, int[]
Returns:int
Method signature:int inequity(int n, int[] gems)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 50 inclusive.
-gems will contain between n and 50 elements inclusive.
-Each element of gems will be between 1 and 100,000 inclusive.
 

Examples

0)
    
1
{5,12,2,9}
Returns: 0
Cut it once anywhere. There is only one segment, and its value if 28. The difference between the worst and best segment is 0 (28 - 28).
1)
    
2
{5,12,9,2}
Returns: 4
Cut it between the 5 and 12, and also between the 12 and 9. The two resulting segments have values 12 and 9+2+5=16.
2)
    
4
{100,92,133,201,34,34,34,94,108}
Returns: 29
Divide it as follows: 108 100 | 92 133 | 201 | 34 34 34 94. Then the result is 225 - 196.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7222&pm=3487

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming