PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Jingbo Shang
Editorialist: Ajay K. Verma
DIFFICULTY:
Easy
PREREQUISITES:
ad-hoc, basic math
PROBLEM:
Given three arrays of positive integers, minimize the maximum element among the three arrays by performing the operation at most M times, where in an operation, all elements of a single array can be halved.
EXPLANATION:
A single operation halves all elements of the array. Hence, the index of the maximum element in the array will remain the same after the operation. This is because of the following observation:
x <= y ==> floor(x/2) <= floor(y/2)
Since, we are only interested in the maximum value after the operations, we do not need to consider all elements of the array, but only its maximum element. Hence, the problem reduces to the following: Given three integers (which are actually the maximum values of the three arrays), apply the operation at most M times such that the maximum of the three integers is minimum; a single operation halves one of the three values.
Order independence and Greedy Approach:
Note that the order in which we apply the operations does not matter as long as the number of operations applied on the three integers remain the same (respectively). In other words, if the initial values of the three integers is (x, y, z) and the number of operations applied on them are (a, b, c), then their final values will be (x/2a, y/2b, z/2c), no matter in which order we apply these operations.
If the value of the three integers is x >= y >= z, and we have some operations left, then at least one of the remaining operations has to be applied on x, otherwise the maximum of the three integers will not change. Since the order in which operations are applied does not matter, we should apply the very first operation on x. This gives us a greedy approach: In each step we should apply the operation on the largest of the three values. The following snippet shows the pseduocode for the greedy approach.
int min_val(int *R, int *G, int *B, int M) {
int x = max(R);
int y = max(G);
int z = max(B);
int arr[] = {x, y, z};
for (int i = 1 to M) {
sort(arr);
// Apply the operation on the largest element
arr[2] /= 2;
}
sort(arr);
return arr[2];
}
Time Complexity:
O (N + M)
Remark about the Original Problem:
In the original version of the problem, a single operation not only halves the elements of a single array, but also increments the elements of other arrays by one.
It can be seen that here the order of operations is relevant, and different order may lead to different results. e.g.,
(5, 3, 1) --> (2, 4, 2) --> (3, 2, 3) --> (4, 3, 1)
(5, 3, 1) --> (6, 1, 2) --> (7, 2, 1) --> (3, 3, 2)
Hence, a greedy approach in this case will not lead to the optimal approach. For the initial set of numbers (7, 8, 4) and number of allowed operations <= 3, the greedy approach will produce 6 as answer.
(7, 8, 4) --> (8, 4, 5) --> (4, 5, 6) --> (5, 6, 3)
while the optimal solution is 5
(7, 8, 4) --> (3, 9, 5) --> (4, 4, 6) --> (5, 5, 3)
A dynamic programming based solution can be used in this case to solve the problem. However, the constraints in the problem were too high for that to run in time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution will be put up soon.