RBLT - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There’s a sequence of N lights. Some of them are red, some are blue, and some haven’t had their colors decided yet.
Is there a way to set the colors of every undecided light to either red or blue, such that there are an equal number of red and blue lights in the end?

EXPLANATION:

First, observe that if N is odd, no matter what we do it’s impossible to make the counts of red and blue lights equal in the end: one count will be odd and the other will be even.
So, in this case the answer is always "No".

Now, suppose N is even.
We then want \frac{N}{2} red and blue lights each, in the end.
Suppose there are already R red and B blue lights.

Since we can’t change the colors of existing lights, the values of R and B can only increase (or remain the same).
In particular, if R \gt \frac{N}{2} initially, it’s definitely impossible to have \frac{N}{2} red lights in the end.
Similarly, if B \gt \frac{N}{2}, it’s impossible to end up with \frac{N}{2} blue lights.

On the other hand, If both R \leq \frac{N}{2} and B \leq \frac{N}{2} hold, it’s always possible to make both equal to \frac{N}{2}: set \frac{N}{2} - R undecided lights to red, and everything else to blue.

In summary,

  • Suppose there are R red lights and B blue lights initially.
  • If N is even, and R and B are both \leq \frac{N}{2}, the answer is "Yes".
  • Otherwise, the answer is "No".

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    c = list(map(int, input().split()))

    if n%2 == 1:
        print('No')
        continue

    red = c.count(1)
    blue = c.count(2)

    if red <= n//2 and blue <= n//2: print('Yes')
    else: print('No')