TopCoder problem "SantaClaus" used in SRM 275 (Division I Level Three)

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.



Method signature:int[] exchange(String[] value)
(be sure your method is public)


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


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.
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.
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.
Returns: {5, 5 }

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , Yarin , vorthys , Olexiy

Problem categories:

Graph Theory, Search