PROBLEM LINK:Author: Praveen Dhinwa DIFFICULTY:Easy PREREQUISITES:adhoc, 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/2^{a}, y/2^{b}, z/2^{c}), 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., 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 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.
This question is marked "community wiki".
asked 13 Oct '14, 14:59

I did the same thing as told in the solution. Even then i was getting WA . It would be great if someone points out what is wrong in the given code . answered 13 Oct '14, 18:51

IS THIS CORRECT SOLUTION FOR THE PREVIOUS QUESTION FOR PRPOTIONS (BEFORE CHANGE) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class potions {
//FIND THE MAXIMUM OF POTIONS FROM THEIR RESPECTIVE COLOUR AND SAVE THAT IN rbg[] for (j = 0; j < 3; j++) {
//CHECK FOR m AND DO SORTING OF rbg[] AND DO THE FOLLWING STEPS FOR EVERY m// /*IF m(REMAINING TRICKS) ARE GREATER THAN 2 THEN WE HAVE TO CHECK WHETHER SECOND MAXIMUM IS GREATER THAN HALF OF FIRST MAXIMUM OR NOT.... IF YES THEN
IF NO THEN
///IF m IS 2 THEN
/// IF m IS 1 THEN
*/
// * INPUT METHODS*////
} answered 13 Oct '14, 19:52

My Solution was giving WA ....please correct me .... http://www.codechef.com/viewsolution/5069774 answered 16 Oct '14, 14:40

Can you please tell what was wrong with the original problem ??
I did the same thing as told in the solution. Even then i was getting WA . It would be great if someone points out what is wrong in the given code . http://www.codechef.com/viewsolution/5082739
Shouldnt the array be sorted once more to display the largest element? Please let me know what is wrong with this : http://www.codechef.com/viewsolution/5105445
@akiitkgp : Yes, you are right. Array should be sorted one more time at the end.