BFLY - Ediorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are R red butterflies, G green butterflies, and B blue butterflies.
There are also an equal number of similarly colored flowers.

Is it possible for each butterfly to sit on a flower that’s colored differently from it?
Each flower can only hold one butterfly.

EXPLANATION:

First, note that if there are too many butterflies of one color, they can’t all sit on a differently colored flower.

For instance, if R \gt G+B, then only G+B red butterflies can sit on green/blue flowers: the rest will be forced to sit on red flowers.
Similarly, if G \gt R+B or B\gt R+G, we run into the same issue.

So, we want all three of:

  • R \leq G+B
  • G \leq R+B
  • B \leq R+G

to hold.

As it turns out, if these three conditions hold, it’s always possible to assign the butterflies appropriately!

How?

Let N = R+G+B be the total number of butterflies.

Suppose all three inequalities hold - another way of seeing this is that all three of R, G, B are \leq \frac{N}{2}.

Arrange the butterflies in a row: first the R red butterflies, then the G green butterflies, then the B blue ones.
Suppose A_i is the color of the i-th butterfly from the left.

Then,

  • If N is even, pair up i and i+\frac{N}{2} for each i \leq \frac{N}{2}.
    For example, if N = 8, the pairs are (1, 5), (2, 6), (3, 7), (4, 8).
    Now, for each pair (x, y), make butterfly x feed on a flower with color A_y, and butterfly y feed on a flower with color A_x.
  • If N is odd, a similar strategy works: pair up i with i + \left\lfloor\frac{N}{2}\right\rfloor.
    This will leave element N unpaired; but it can be taken into a triple with 1 and 1 + \left\lfloor\frac{N}{2}\right\rfloor instead.

This works because we arranged the butterflies in order first, and only then paired each one with a color that’s \frac{N}{2} away from it.
Since all of R, G, B are \leq \frac{N}{2}, this ensures that no two pairs have elements of the same color, which is what we want.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    r, g, b = map(int, input().split())
    mx = max(r, g, b)
    if mx > r+g+b-mx: print('No')
    else: print('Yes')