Connection Status:
Competition Arena > Necklaces

Necklaces

SRM 247 · 2005-06-18 · by dgoodman

SRM 247 · 2005-06-18 · by dgoodman · Dynamic Programming
Class Name: Necklaces
Return Type: int
Method Name: inequity
Arg Types: (int, vector<int>)
Problem Statement

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.

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.

3)
4
{100,107,103,109,103,102,110,140,190,130,120,200,
 300,109,108,107,106,155,144,103,108,300,400,130,
 120,140,230,150,110,107,102,100,100,100,100,100,
 100,100,100,100,100,100,100,100,100,100,100,100,100,100}
Returns: 25
4)
5
{100,107,103,109,103,102,110,140,190,130,120,200,
 300,109,108,107,106,155,144,103,108,300,400,130,
 120,140,230,150,110,107,102,100,100,100,100,100,
 100,100,100,100,100,100,100,100,100,100,100,100,100,100}
Returns: 52

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

Coding Area

Language: C++17 · define a public class Necklaces with a public method int inequity(int n, vector<int> gems) · 70 test cases · 2 s / 256 MB per case

Submitting as anonymous