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

A sequence is called good if its elements alternate in parity between even and odd.

You’re given an array A. Find the length of its longest subsequence that can be rearranged to be made good.

EXPLANATION:

Since a good sequence alternates between even and odd values, it must have an approximately equal count of both types of elements.

In particular, observe that in a good sequence, the difference between the number of even elements and the number of odd elements is at most 1.

Now, observe that if we take any sequence with the difference in number of even and odd elements being at most 1, it’s always possible to rearrange it into a good sequence.

  • If the even and odd counts are equal, we have the same count of each so just alternate them.
  • If the counts are not equal, then one count is larger than the other by exactly 1.
    Suppose the odd count is larger, then it can be arranged into odd, even, odd, even, …

So, the goal is to find the longest subsequence such that it has an almost-equal number of odd and even elements.

Suppose there are E even elements and O odd elements in A.

Then,

  • If E = O, we can take all of them. The answer is 2E.
  • If E \lt O, then we can at best take E even elements and E+1 odd elements.
    The answer is 2E+1.
  • If E \gt O, then we can at best take O odd elements and O+1 even elements.
    The answer is 2O+1.

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 x in a:
        if x%2 == 0: even += 1
        else: odd += 1
    
    if odd <= even: print(min(even, odd+1) + odd)
    else: print(min(odd, even+1) + even)