You are not logged in. Please login at www.codechef.com to post your questions!

×

PRPOTION-Editorial

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.

This question is marked "community wiki".

asked 13 Oct '14, 14:59

djdolls's gravatar image

6★djdolls
2.2k508484
accept rate: 0%

edited 10 Nov '14, 01:40

admin's gravatar image

0★admin ♦♦
18.9k348495531

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

(13 Oct '14, 15:57) abcdexter242★

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) goltu3★

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) akiitkgp3★

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

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

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

link

answered 13 Oct '14, 19:22

waquar1234's gravatar image

3★waquar1234
161
accept rate: 0%

I removed the condition even then I am getting WA .

(13 Oct '14, 21:02) goltu3★

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

link

answered 14 Oct '14, 07:27

roman28's gravatar image

4★roman28
1.6k71429
accept rate: 19%

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

link

answered 13 Oct '14, 18:51

goltu's gravatar image

3★goltu
2624
accept rate: 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;
}

}

link

answered 13 Oct '14, 19:52

shubham011's gravatar image

5★shubham011
1783617
accept rate: 0%

edited 15 Oct '14, 12:46

Format your code properly.

(13 Oct '14, 23:45) nisargshah953★

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

link

answered 14 Oct '14, 07:16

roman28's gravatar image

4★roman28
1.6k71429
accept rate: 19%

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

link

answered 16 Oct '14, 14:40

ajay154's gravatar image

3★ajay154
1.6k72044
accept rate: 8%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×14,361
×3,155
×864
×319

question asked: 13 Oct '14, 14:59

question was seen: 3,428 times

last updated: 10 Nov '14, 01:41