Problem Statement
Aqa Asadi holds regular coding championships between his students. There are N students who want to take part in the next coding championship. All N students are sitting along one long desk in the computer lab. Aqa Asadi wants to divide the students into exactly k groups. Each group must be contiguous, so that the students in the group can talk to each other during the contest without disturbing the other groups. The groups should be as balanced as possible, as defined below.
You are given the int[] Skills with N elements: for each student, in the order in which they are sitting, their skill in coding. The skill of a group is simply the sum of skills of all students it contains. Let S be the sum of all skills. Clearly, if we had k groups that are all equally good, the ideal skill of each group would be S / k. Thus, let's define the badness of a group as the square of the difference between the ideal skill of a group and its actual skill. I.e., if the actual skill of a group is G, its badness is (S / k - G)^2. Finally, the total badness of a particular division into groups is computed by adding together the badness for each group in the division.
Calculate the smallest possible total badness. Return that value multiplied by k^2. (It can be shown that this value is always an integer.)
Definition
- Class:
- AqaAsadiGroups
- Method:
- minimumDifference
- Parameters:
- int[], int
- Returns:
- long
- Method signature:
- long minimumDifference(int[] Skills, int k)
- (be sure your method is public)
Constraints
- Skills will contain between 1 and 500 elements, inclusive.
- Each element of Skills will be between 1 and 4000, inclusive.
- k will be between 1 and 500, inclusive.
Examples
{1, 2}2
Returns: 2
The optimal split of {1, 2} into two groups is to split it into {1} and {2}. The average skill of a group is S/k = 3/2. Thus, the individual groups have badness (3/2 - 1)^2 and (3/2 - 2)^2. The total badness is therefore 1/4 + 1/4 = 1/2, and we should return the value (1/2) * k^2 = (1/2)*4 = 2.{1, 2}1
Returns: 0
The only way of splitting {1, 2} into just one group is to leave {1, 2} as the only group. Its badness is zero.{1, 2, 3, 4}2
Returns: 8
One optimal split is into {1, 2, 3} and {4}. Each group has badness 1, the total badness is 2, and the correct return value is 2 * k^2 = 8. Note that the groups must be contiguous, so we cannot divide the input into {2, 3} and {1, 4}.{1, 2}5
Returns: 80
One optimal split is into the following five groups: {1}, {}, {2}, {}, {}. Note that some groups must be empty, as k is greater than the number of students. The average skill of a group is S/k = 3/5. Thus, the individual groups have badness (3/5 - 1)^2, (3/5 - 0)^2, (3/5 - 2)^2, (3/5 - 0)^2, (3/5 - 0)^2. The total badness is therefore 16/5, and we should return the value (16/5) * k^2 = 16*5 = 80.