CDX1601 - Editorial

general
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Puneet Gupta
Editorialist: Puneet Gupta

DIFFICULTY:

EASY

PREREQUISITES:

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.