Connection Status:
Competition Arena > SantaClaus

SantaClaus

SRM 275 · 2005-11-30 · by dgoodman

SRM 275 · 2005-11-30 · by dgoodman · Graph Theory, Search
Class Name: SantaClaus
Return Type: int[]
Method Name: exchange
Arg Types: (vector<string>)
Problem Statement

Problem Statement

The spirit of Christmas is most apparent in the exchanging of presents! Santa Claus would like software to make this unnecessary. He has already decided which present should be given to each person, but he is wondering if he could make adjustments.

Specifically he has estimated the intrinsic value of each present to each person. He wants software to determine if there is a group of people whose total value would be increased by redistributing the gifts within the group. Some people might end up with a worse present, but the total value is what Santa must consider. If such a group exists, Santa would like to know the size of the smallest such group, and how much the total value of their presents can be increased by.

The intrinsic value of the presents to each person is given in a String[] value. Each character in each element of value is an uppercase letter, with 'A' signifying a value of 1, 'B' a value of 2, etc. The j-th character in the i-th element of value is the value of the j-th present to the i-th person.

The original intent of Santa was to give the first present to the first person, the second present to the second person, etc. Create a class SantaClaus that contains a method exchange that is given the String[] value and returns a int[] containing two elements: the first element is the size of the smallest improvable group, and the second is the amount by which their total value can be increased. Report the largest possible increase in value for a group of that size. If there is no improvable group, return 0 in both elements.

Constraints

  • value will contain n elements, where n is between 2 and 50 inclusive.
  • Each element of value will contain n characters, each being an uppercase letter 'A'-'Z'.
Examples
0)
{"ABCDE","ABCDE","ABCDE","ABCDE","ABCDE"}
Returns: {0, 0 }

Each present has the same value to everybody, so there is no way to increase the total value by reassigning the presents.

1)
{"ABC","BCD","ZAB"}
Returns: {2, 26 }

The third person would really like the first present. So we could exchange presents between the first person and the third person. Previously, the values were 1 (first person) + 2 (third person) = 3. After the exchange the values become 3 (first person) + 26 (third person) = 29. So the net gain is 29-3 = 26.

2)
{"BCAAA","ADEAA","AAXYA","AAAKL","EAAAD"}
Returns: {3, 1 }

The first, fourth, and fifth persons can exchange presents, giving up values of 'B', 'K', and 'D' and acquiring values of 'A', 'L', and 'E'. The first person loses net value of 1, but each of the others gains 1.

3)
{"VWAAA","ADEAA","AAXYA","AAAKL","EAAAD"}
Returns: {5, 5 }
4)
{"VWAAA","ADEAA","AAXYA","AAAKL","EAAZD"}
Returns: {2, 23 }

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 SantaClaus with a public method vector<int> exchange(vector<string> value) · 29 test cases · 2 s / 256 MB per case

Submitting as anonymous