Recently I participated in Crossover Senior Architect Tournament.
The third problem was scored in 75 points and it was a little bit unclear. Most of participants who were eligible to continue scored equally on this problem getting 56 points of 75.
The problem description is below.
Shrinking Number Line
We have an array of n integers, point, and an integer, k. We can perform either of the following operations once for each point[i] in point:
Increment point[i] by k.
Decrement point[i] by k.
We want to perform an operation on each point[i] such that the difference between the maximum and minimum values in the array after performing all operations is minimal.
Complete the minimize function in the from the provided code. It has two parameters:
An array of n integers, point, where the value of each element corresponds to a point on the number line.
An integer, k, denoting the value that each element must either be incremented or decremented by.
The function must perform one operation on each pointi such that the absolute difference between the maximum and minimum values in the modified point array is minimal, then return an integer denoting the minimal difference between the modified array’s new maximum and minimum values.
Input Format
The provided code reads the following input from stdin and passes it to the function:
The first line contains an integer, n, denoting the number of elements in the point array.
Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer describing point[i].
The last line contains an integer, k.
Constraints
1 ≤ n ≤ 100
1 ≤ k ≤ 10^5
-10^5 ≤ point[i] ≤ 10^5
Output Format
The function must perform one operation on each pointi such that the absolute difference between the maximum and minimum values in the modified point array is minimal, then return an integer denoting this minimal difference between the array’s new maximum and minimum values. This is printed to stdout by the provided code.
Sample Input 0
3
-3
0
1
3
Sample Output 0
3
Explanation 0
We have point = [-3, 0, 1] and k = 3. If we add k to the first element and subtract it from the latter two elements, we get point = [-3 + 3, 0 − 3, 1 − 3] = [0, -3, -2]. We then take the absolute difference between the maximum and minimum values in point, which is |0 − -3| = 3, and return 3 as our answer.
Sample Input 1
3
4
7
-7
5
Sample Output 1
4
Explanation 1
We have point = [4, 7, -7] and k = 5. If we subtract k from the first and second elements and add k to the third element, we get point = [4 − 5, 7 − 5, -7 + 5] = [-1, 2, -2]. We then take the absolute difference between the maximum and minimum values in point, which is |-2 − 2| = 4, and return 4 as our answer.
Sample Input 2
2
-100000
100000
100000
Sample Output 2
0
Explanation 2
We have point = [-100000, 100000] and k = 100000. If we add k to the first element and subtract k from the second element, we get point = [-100000 + 100000, 100000 − 100000] = [0, 0]. We then take the absolute difference between the two values in point, which is |0 − 0| = 0 as there are only two elements, and return 0 as our answer.
Codejam Analysis 