EVENHATE - 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:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given an array A, which can be rearranged as you like.
Maximize the number of odd prefix sums of A.

EXPLANATION:

Let P_i = A_1 + A_2 + \ldots + A_i denote the i-th prefix sum of A.
The parity of an integer denotes whether it’s even or odd.

Note that:

  • If A_i is even, then P_i and P_{i-1} have the same parity.
  • If A_i is odd, then P_i and P_{i-1} have different parities.

We start at P_0 = 0 which is even, and then each odd number that appears switches the parity from even to odd or vice versa.

So, if there are k odd numbers in A, no matter how they’re rearranged, the parity will switch exactly k times.
Out of these k switches, \text{ceil}\left(\frac{k}{2}\right) of them will lead to odd numbers, since the very first switch is to an odd number.

That leaves us with N-k even numbers.
These we can simply place after the first odd number: each of them will then lead to one additional odd prefix, for another N-k.
So, if there are k odd numbers in A, the maximum number of odd prefix sums is

N-k + \text{ceil}\left(\frac{k}{2}\right)

There is one edge case: when k = 0, the answer is 0 since we can’t get any odd prefix sums by just adding even numbers.

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()))
    odd, even = 0, 0
    for i in range(n):
        if a[i]%2 == 0: even += 1
        else: odd += 1
    
    if odd == 0: print(0)
    else: print(even + (odd + 1)//2)
1 Like