PROBLEM LINK:
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
PROBLEM:
Beauty of an array is defined as the difference between the largest and smallest element in the array. An array is called good if its elements can be partitioned into two non-empty, disjoint arrays such that the beauties of both arrays are equal.
Given an array A of N integers. In one move, you may add or subtract any element by 1. Determine the minimum number of moves to make array A good.
EXPLANATION:
Sort array A in non-decreasing order. Then A_1\le A_2\le \dots \le A_N.
Say we have partitioned the elements of A (without making any updates to the elements) into two non-empty arrays B_1 and B_2 in some optimal fashion.
Now, we concern ourselves with applying the least number of moves on the elements of B_1 and B_2 to make their beauties equal.
Note: We assume both B_1 and B_2 have \ge 2 elements in them. The case where either contains exactly one element is tackled at the end.
Observation: It suffices to only apply moves on either B_1 or B_2.
Observation: It suffices to only increase/decrease the values of the largest/smallest elements of the array.
Thus, we can only keep one greatest and smallest element in each of B_1 and B_2, and safely discard the rest of the elements from them.
Let B_1 = [A_w,A_x]\ (w<x) and B_2 = [A_y, A_z]\ (y<z).
Observation: Either (but not both) of w or y is equal to 1.
Observation: Either (but not both) of x or z is equal to N.
Then, a bit of casework shows that the following are the only unordered possibilities for the elements of B_1 and B_2 (where 1<i<j<N) -
(Proof of why these are the only cases is mundane, and left to the reader as an exercise).
Now that we know what arrays B_1 and B_2 look like, we can emulate each of them and find the least possible moves required. For each of the above cases, iteratively try every valid value of A_i, and find the best value for A_j, to minimize the difference of the beauties.
This can be done efficiently using binary search (lower_bound
to be precise), in O(\log N) for each valid value of A_i.
How?
We only discuss the first case; all other cases can be done similarly.
Say we have fixed the value of i (and are trying to find the best j). Then the difference of the beauties of B_1 and B_2 is equal to:
Then, minimising the difference is equivalent to finding an A_j that is closest to the value A_1+A_N-A_i, which can be done by running a lower bound on A and finding the best value around it.
The case that that stumped many (me included!) is when B_1 or B_2 consisted of exactly 1 element. In this case, the beauty of that array always equals 0.
Therefore, we have to make the beauty of the other array (which consists of all but one elements of A) equal 0, by applying moves on its elements to make them all equal.
More formally, we need to apply the least number of moves on the array [A_1,\dots,A_{i-1},A_{i+1},\dots,A_N] to make all elements equal. The answer is then updated with the minimum of this value, over all i.
This is a slightly modified version of a classical problem, which can be solved efficiently in O(N) using suitable preprocessing!
TIME COMPLEXITY:
Sorting array A takes O(N\log N). Computing the 3 cases (mentioned in the editorial) takes O(3\cdot N\log N). Finally, computing the edge case takes O(N). The total time complexity is therefore:
per test case.
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters