NODDSM - 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 are N numbers written on a blackboard, each of which is either 1 or 2.
You can do the following:

  • Split a 2 into two ones.
  • Combine two ones into a 2.

Find the minimum number of operations needed so that no pair of numbers written on the blackboard has an odd sum.

EXPLANATION:

Observe that if the blackboard has both an occurrence of 1 as well as an occurrence of 2, taking their sum will result in 1+2 = 3 which is odd.
So, in the end, the blackboard must have either all ones, or all twos.
Both cases are fine: if everything is 1 then every sum is 2 (even), and if everything is 2 then every sum is 4 (also even).

Let’s look at both cases.
First, suppose we want all ones.
Our only option in this case is to use the move that turns a 2 into two ones.
This must be applied once for every 2 initially on the blackboard.
So, the number of moves needed is \text{count}(2).

Next, suppose we want all twos.
Our only option now is the other move: turning two ones into a 2.
Here, note that:

  • If the number of ones is odd, it’s never possible to turn all of them into twos - because in the end we’ll be left with a single unpaired 1.
  • If the number of ones is even, then we’ll need \frac{\text{count}(1)}{2} operations, since each operation pairs off two ones into a single 2.

Thus, the answer is just the minimum of \text{count}(2) and \frac{\text{count}(1)}{2}, with the latter being applicable only when \text{count}(1) is even.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    ans = a.count(2)
    if a.count(1) % 2 == 0:
        ans = min(ans, a.count(1) // 2)
    print(ans)