PERMGE2 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

There’s an array of length N containing X zeros, Y ones, and Z twos.
Is there a way to rearrange it to obtain A_i + A_{i+1} \geq 2 for each 1 \leq i \lt N?

EXPLANATION:

We have the integers 0, 1, 2, and want the sum of adjacent elements to be at least 2.
That means each 0 can only be adjacent to a 2, and each 1 can be adjacent to either a 1 or a 2.

Let’s work with just the 0‘s and $2’$s first.
Each 0 must be adjacent to a 2, so the best we can do is to alternate them, i.e. arrange them as [0, 2, 0, 2, 0, 2, \ldots]
Since there are X zeros, we need at least X-1 twos to achieve this.

So, if Z \lt X-1, we can immediately say the answer is No.
Now we deal with Z \geq X-1.

First, suppose Z = X-1.
Then, the only valid arrangement is [0, 2, 0, 2, \ldots, 0, 2, 0], i.e. an alternating sequence that begins and ends with 0.
If we do this though, there’s no way to place any ones at all: anywhere we place a 1, it’ll be adjacent to a 0 (giving a sum of 1).
So, in this case, if Y = 0 we’ve obtained a solution, and if Y \gt 0 there’s no solution.

That leaves the case of Z \geq X.
In this case, it’s always possible to form a valid rearrangement.
One way is as follows:

  • First, start with the array [0, 2, 0, 2, \ldots, 0, 2], i.e. an alternating sequence of X zeros and X twos that starts with 0 and ends with 2.
  • Next, place all the ones at the end, to obtain [0, 2, \ldots, 0, 2, 1, 1, \ldots, 1, 1].
  • Then, place all remaining twos at the end, to obtain [0, 2, \ldots, 0, 2, 1, 1, \ldots, 1, 1, 2, 2, \ldots, 2, 2].

It’s easy to see that this is a valid array.

In summary, we have a few different cases:

  • If Z \lt X-1, the answer is No.
  • If Z = X-1 and Y \gt 0, the answer is No.
  • In all other cases, the answer is Yes.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    x, y, z = map(int, input().split())
    
    if x > z+1: print('No')
    elif x == z+1 and y > 0: print('No')
    else: print('Yes')