# 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[0], a[1], a[2]` and sort them in ascending order. We’ll now have `a[0] <= a[1] <= a[2]`.

There are two case:

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

2. `2*(a[0]+a[1]) > a[2]`. In this case, we can continuously take a set of two balloon from `a[2]` and a balloon from `max(a[0], a[1])` until a point that `a[2] <= max(a[0], a[1])`. At this point, `max(a[0], a[1])-a[2] <= 1`, and since `max(a[0], a[1]) - min(a[0], a[1]) <= 1` too, `max(a[0], a[1], a[2]) - min(a[0], a[1], a[2]) <= 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[0]+a[1]+a[2])%3` doesn’t change, so there will be at most `(a[0]+a[1]+a[2])% 3` balloons wasted. We go back to the beginning now. The answer is `(a[0]+a[1]+a[2])/3`.

# AUTHOR’S SOLUTION:

Author’s solution can be found here.

//