Connection Status:
Competition Arena > BagsOfGold

BagsOfGold

SRM 228 · 2005-01-27 · by dgoodman

SRM 228 · 2005-01-27 · by dgoodman · Dynamic Programming, Recursion
Class Name: BagsOfGold
Return Type: int
Method Name: netGain
Arg Types: (vector<int>)
Problem Statement

Problem Statement

My partner and I have bags of gold, lined up in a row. The bags are different sizes. My partner has offered to split up the gold using the following system: we take turns, each time choosing one bag from either end of the line. She has even generously offered to let me go first -- hmmmmmmmm....

I need software to tell me the total amount of gold that I will get compared to how much my partner will get if I choose first. Of course we will assume that my partner and I are brilliant and always choose in the optimum way.

Create a class BagsOfGold that contains a method netGain that is given a int[] bags, the values of all the bags of gold in the order in which they are lined up. It should return how much more gold I will get than my partner if we both behave optimally. (I fear that the answer might be a negative number since my partner proposed the plan.)

Constraints

  • bags will contain between 1 and 50 elements inclusive.
  • Each element of bags will be between 1 and 100,000 inclusive.
Examples
0)
{7,2}
Returns: 5

I will choose the 7, and then she gets the 2. So the result is 7 - 2 = 5.

1)
{2,7,3}
Returns: -2

It doesn't matter whether I choose the 2 or the 3. She will choose the 7 and I will get the remaining bag. (2+3) - 7 = -2

2)
{1000,1000,1000,1000,1000}
Returns: 1000

Since I choose first I will get 3 bags and my partner will get only 2 bags. They all have the same value so (1000+1000+1000) - (1000+1000) = 1000.

3)
{823,912,345,100000,867,222,991,3,40000}
Returns: -58111
4)
{23,35,12,100000,99234,86123,3245}
Returns: -83644

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

Coding Area

Language: C++17 · define a public class BagsOfGold with a public method int netGain(vector<int> bags) · 29 test cases · 2 s / 256 MB per case

Submitting as anonymous