PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You have A orange strips, B white strips, and C green strips.
Is it possible to arrange all of them in such a way that no two strips of the same color are next to each other?
EXPLANATION:
Intuitively, if there are “too many” strips of a single color, we’ll be forced to place two of them next to each other no matter what.
Let M = \max(A, B, C) be the maximum number of same-color strips.
Let S = A+B+C be the total number of strips.
If M is more than about half of S, we’ll cannot avoid placing two strips of that color next to each other.
Specifically, if 2M \gt S+1 we have a problem; otherwise it’s always possible to place the strips appropriately.
Proof
Without loss of generality, let A \geq B \geq C, so that M = A.
Let’s name the positions 1, 2, 3, \ldots, A+B+C.
Then,
- Place A orange strips at positions 1, 3, 5, 7, \ldots, 2A-1.
- Place B white strips at positions 2A+1, 2A+3, \ldots till it’s not possible to place any more.
Then, start placing them at 2, 4, 6, \ldots. - Finally, place the green strips in the remaining positions (which are guaranteed to be even-indexed).
Since 2A \leq S+1 (by assumption), we have 2A-1 \leq S, meaning all the orange strips are at odd indices. No two of them can be adjacent.
Then, the white strips will be on the last remaining odd positions, and then some starting even positions. No two of these can be next to each other.
Finally, the green strips will be at only even positions; they definitely can’t be next to each other.
This gives us a fairly simple check: print Yes if 2\cdot\max(A, B, C) \gt A+B+C+1, and No otherwise.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
a, b, c = map(int, input().split())
print('Yes' if 2*max(a, b, c) <= a+b+c+1 else 'No')