A. Number Assignment
Author: Suhendry Effendy
(link to problem A)
This problem supposed to be the easiest problem in this contest.
First, notice that we can ignore all duplicate numbers as putting two same numbers in one group costs nothing. Next, observe that each group in the optimal partition will contain adjacent numbers. By adjacent I mean the nearest next or previous number in the given list. Therefore, to solve this problem, first we need to sort the given numbers.
There are two main approaches to form the partition: greedy approach and dynamic programming.
This is the simplest approach. Starts with A[N] – A as the cost (note that A has been sorted, thus A[N] is the largest element while A is the smallest). Next, find the largest M – 1 gap between numbers (gap = difference between two adjacent numbers in the sorted list) and substracts the initial cost with this number; this is the answer to the problem.
To understand why this approach works, consider these three figures. Let the sorted given numbers are 2, 3, 6, 7, 8 and 10.
The gaps between adjacent numbers in the sorted list are:
: 2 -(1)- 3 -(3)- 6 -(1)- 7 -(1)- 8 -(2)- 10
: 1, 3, 1, 1, 2
Note that for M groups, there will be M-1 gaps. In order to minimize the total cost of the partition (number assignment), we need to maximize the total gaps, thus removing the M-1 highest gap will produce the partition with the smallest cost.
This approach has O(N lg N) time complexity.
Instead of analysing which gaps we should remove, we can “try all combination” using dynamic programming approach. The simplest idea (which I can think) for this approach needs O(N2) space and O(N3) time complexity. We need to keep the smallest element which has not been grouped and the number of group left to be form as the DP state/dimension; for each state, we need to iterate through ungrouped elements and “try” to create a group up to that element.
As the constraint for this problem is quite small (N <= 100), this approach will get accepted.
The reason I set the constraint to be small is because I don’t want to bother myself with big input file for such easy problem. However, to my surprise, most of the teams (if not all) used dynamic programming approach.