 # CDX1601 - Editorial

Author: Puneet Gupta
Editorialist: Puneet Gupta

EASY

Greedy

# PROBLEM:

Given the number of R, G and B ballons, find the maximum number N of tables, that can be decorated so that three balloons attached to some table shouldn’t have the same color.

# EXPLANATION:

The order of the balloons isn’t important, so instead or r, g, b, we’ll call them `a, a, a` and sort them in ascending order. We’ll now have `a <= a <= a`.

There are two case:

1. `2*(a+a) <= a`. In this case, we can take `a` sets of (1, 0, 2) and `a` sets of (0, 1, 2), so the answer is `a+a`.

2. `2*(a+a) > a`. In this case, we can continuously take a set of two balloon from `a` and a balloon from `max(a, a)` until a point that `a <= max(a, a)`. At this point, `max(a, a)-a <= 1`, and since `max(a, a) - min(a, a) <= 1` too, `max(a, a, a) - min(a, a, a) <= 1`. All we have to do is take all possible (1, 1, 1) group left. Since we only take the balloons in group of 3, `(a+a+a)%3` doesn’t change, so there will be at most `(a+a+a)% 3` balloons wasted. We go back to the beginning now. The answer is `(a+a+a)/3`.

# AUTHOR’S SOLUTION:

Author’s solution can be found here.