×

# PRPOTION-Editorial

Author: Praveen Dhinwa
Tester: Jingbo Shang
Editorialist: Ajay K. Verma

Easy

# 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];
}


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.

This question is marked "community wiki".

6★djdolls
2.2k518484
accept rate: 0%

19.3k348495534

Can you please tell what was wrong with the original problem ??

(13 Oct '14, 15:57)

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

(13 Oct '14, 15:58) 3★

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

(13 Oct '14, 17:29) 3★

@akiitkgp : Yes, you are right. Array should be sorted one more time at the end.

(13 Oct '14, 17:52) 5★

 1 @goltu m<=100. I think you should remove "if(m>=30) m=30;" from your code and it will be accepted answered 13 Oct '14, 19:22 16●1 accept rate: 0% I removed the condition even then I am getting WA . (13 Oct '14, 21:02) goltu3★
 1 @akiitkgp You are not making the maxr, maxg and maxb equal to 0 after every test case. This is the AC version of your code. answered 14 Oct '14, 07:27 4★roman28 1.6k●7●14●29 accept rate: 19%
 0 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 answered 13 Oct '14, 18:51 3★goltu 26●2●4 accept rate: 0%
 0 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 { public static void main(String[] args) throws IOException { int i, t = input(); for (i = 0; i < t; i++) { int o[] = new int[4]; input(o, 4); int j, m = o[3]; long rbg[] = new long[3];  //FIND THE MAXIMUM OF POTIONS FROM THEIR RESPECTIVE COLOUR AND SAVE THAT IN rbg[] for (j = 0; j < 3; j++) {  long a[] = new long[o[j]]; rbg[j] = input(a, o[j]); } //SORT THE ARRAY rbg AND SAVE THE MAXIMUM OF THREE IN max// Arrays.sort(rbg); long max = rbg[2];  //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  CHECK THE SAME FOR THIRD MAXIMUM IS GREATER THAN HALF OF SECOND MAXIMUM OR NOT ... NOW IF YES THEN HALF THE THIRD ONE FIRST AND INCREASE THE OTHER TWO .. IF NO THEN HALF THE SECOND ONE FIRST AND INCREASE OTHER TWO ....  IF NO THEN  HALF THE MAXIMUM AND INCREASE THE OTHER TWO....  ///IF m IS 2 THEN THEN CHECK ONLY FOR SECOND MAXIMUM .... IF YES THEN HALF THE SECOND MAXIMUM OTHERWISE HALF THE MAXIMUM AND REST WORK...  /// IF m IS 1 THEN HALF THE MAXIMUM AND REST... BUT WE NEED TO RECORD THE MAXIMUM'S MINIMUM VALUE( long max) OF ALL STEPS BECAUSE IF MAXIMUM DOESN'T REDUCE AFTER m-2 or m-1 TRICKS THEN WE NOT NEED TO DO ALL TRICKS  */  while ((m) > 0) { if (m >= 3) { if (rbg[1] >= (rbg[2] / 2)) { if (rbg[0] >= (rbg[1] / 2)) { rbg[0] /= 2; rbg[2]++; rbg[1]++; } else { rbg[1] /= 2; rbg[2]++; rbg[0]++; } } else { rbg[2] /= 2; rbg[0]++; rbg[1]++; } } else if (m == 1) { rbg[2] /= 2; rbg[0]++; rbg[1]++; } else if (m == 2) { if (rbg[1] >= rbg[2] / 2) { rbg[1] /= 2; rbg[2]++; rbg[0]++; } else { rbg[2] /= 2; rbg[0]++; rbg[1]++; } } Arrays.sort(rbg); if (rbg[2] < max) max = rbg[2]; m--; } System.out.println(max); } }  // * INPUT METHODS*//// static BufferedReader br = new BufferedReader(new InputStreamReader( System.in)); private static String s[]; public static void input(int a[], int n) throws IOException { s = br.readLine().split(" "); int i; for (i = 0; i < n; i++) { a[i] = Integer.parseInt(s[i]); } } public static long input(long a[], int n) throws IOException { s = br.readLine().split(" "); int i; long max = 0; for (i = 0; i < n; i++) { a[i] = Integer.parseInt(s[i]); if (max < a[i]) max = a[i]; } return max; } public static int input() throws IOException { int n; n = Integer.parseInt(br.readLine()); return n; }  } answered 13 Oct '14, 19:52 178●3●7●17 accept rate: 0% Format your code properly. (13 Oct '14, 23:45)
 0 @goltu Dude the order of input is red green and blue. check your order of input ans also why are using the following statement: if(m>30) m=30; remove this statement. Check this. It the AC version of your code. answered 14 Oct '14, 07:16 4★roman28 1.6k●7●14●29 accept rate: 19%
 0 My Solution was giving WA ....please correct me .... http://www.codechef.com/viewsolution/5069774 answered 16 Oct '14, 14:40 3★ajay154 1.6k●7●20●44 accept rate: 8%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,005
×3,393
×919
×319

question asked: 13 Oct '14, 14:59

question was seen: 3,514 times

last updated: 10 Nov '14, 01:41