PRPOTION-Editorial

easy
editorial
greedy
oct14

#1

PROBLEM LINK:

Practice
Contest

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.


#2

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


#3

@goltu m<=100.
I think you should remove “if(m>=30)
m=30;” from your code and it will be accepted


#4

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* = Integer.parseInt(s*);
	}

}

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* = Integer.parseInt(s*);
		if (max < a*)
			max = a*;

	}
	return max;
}

public static int input() throws IOException {
	int n;
	n = Integer.parseInt(br.readLine());
	return n;
}

}


#5

@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.


#6

@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.


#7

My Solution was giving WA …please correct me … http://www.codechef.com/viewsolution/5069774


#8

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


#9

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


#10

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


#11

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


#12

I removed the condition even then I am getting WA .


#13

Format your code properly.