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.



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


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


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).
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.
Returns: 29
Divide it as follows: 108 100 | 92 133 | 201 | 34 34 34 94. Then the result is 225 - 196.

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming