CODEWITHSUNDEEP
c++algorithmlogic
user8386434
user8386434

Reputation:

Given 3 positive integers, find max number of steps to reduce them to 0

I am solving this question from CodeForces:

We are given three values, r, g and b which represent number of Red, Green and Blue candies in three piles, respectively. Tanya can't eat two candies of the same color in a day i.e., each day she eats exactly two candies of different colors. Find the maximal number of days Tanya can eat candies.

I did it in a simple way as below:

int main() {
    int t, r, g, b;
    cin>>t;

    while(t--) {
        int counter=0;
        cin >> r >> g >> b;

        while(r && g) {
            r--;
            g--;
            counter++;
        }

        while(g && b) {
            g--;
            b--;
            counter++;
        }

        while(r && b) {
            r--;
            b--;
            counter++;
        }

        cout<<counter<<"\n";
    }

    return 0;
}

However, it breaks on the inputs 7 4 10 and 8 2 8. My code returns 7 and 8 respectively, instead of 10 and 9 (I am unsure how 10 and 9 are the expected answers for the inputs). The editorial talks about sorting the input and checking if b <= r + g and returning (r+g+b)/2 if true and r+g otherwise. Suffice to say, I am unable to understand what the editorial says.

Could someone please point out why my logic is incorrect and what am I missing?

Thanks!

Upvotes: 3

Views: 198

Answers (2)

Anatolii
Anatolii

Reputation: 14670

Even if your solution is corrected it may not pass all the tests on codeforces as its time complexity is proportional to values of your input numbers. But there exists a solution that has a constant running time regardless of the input numbers.

First, sort 3 input numbers. IF they are not sorted then on each iteration we would need to find maximum and minimum elements and then decrement them. If the numbers are sorted then we know right away where the largest and smallest numbers are and so we can decrement them immediately.

Now, after sorting let's consider possible cases for a,b,c: a<=b<=c:

0.if a is 0 (or a,b or a,b,c) then the number is obviously min(b,c).

1.For a, b, c: b = c, a > 0 it's always better to decrement a,b then a,c in turns as it yields to the maximum number of iterations. For instance, 2,3,3 -> 1,2,3 -> 0,2,2 -> 0,1,1 -> 0,0,0. If a = c and b = c then it' still true - 2,2,2 -> 1,1,2 -> 0,1,1 -> 0,0,0.

2.For a, b, c: a != b and b != c we should keep in mind case 1 that maximises the number of iterations. How to get there? Well, by decrementing c and a as long as either a becomes 0 (then case 1 isn't needed as we can already calculate the remaining steps as min(b, c - a)) or c becomes equal to b and then it's case 1. If we try to decrement any other pair of numbers then the numbers of iterations will decrease as b will be decreased for no good reason :). After this we can apply case 1.

3.This approach can be implemented in O(1) time complexity.

...    

int main() {
    int t;
    std::cin >> t;

    for (int i = 0; i < t; i++) {
        std::vector<int32_t> array(3);
        for (int32_t& value : array) {
            std::cin >> value;
        }
        std::sort(array.begin(), array.end());
        int32_t days = 0;

        int32_t diff = array[2] - array[1];
        days += (std::min(array[0], diff));
        array[0] -= days;
        array[2] -= days;

        array[2] -= array[0] / 2;
        days += (array[0] / 2);

        array[1] -= array[0] / 2;
        days += (array[0] / 2);

        days += std::min(array[1], array[2]);

        std::cout << days << std::endl;
    }

    return 0;
}

...

Upvotes: 1

2997ms
2997ms

Reputation: 26

Because you need to find the optimal method for this problem.

For example, 1,1,10, the optimal way is to r & b, g & b. In your method, it is only 1 as the result.

Thus we need to sort the three values and always use the biggest number to reach the answer.

Upvotes: 1

Related Questions