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

An array B is good if B_i\bmod 2 \neq B_{i+1}\bmod 2 for all i.
Given an array A, find the length of its longest good subsequence.

EXPLANATION:

We only care about each A_i modulo 2.
So, replace A_i with 0 if it’s even and 1 if it’s odd.
For example, A = [2, 5, 3, 6, 2, 1] turns into [0, 1, 1, 0, 0, 1].

After this reduction, a subsequence is good if and only if it doesn’t contain two adjacent equal characters.
That is, a good subsequence must look like either 010101\ldots or 101010\ldots

The longest such subsequence can be found greedily, using the following algorithm:

  1. Always choose A_1.
  2. Let p denote the index of the last chosen element.
    Initially, p = 1.
  3. Then, for each i from 2 to N in order, if A_i \neq A_p, include A_i into the subsequence.
    If A_i is included, update p to equal i and increment the answer by 1.

There are other ways to look at this as well - for example, the answer is equal to the number of contiguous “blocks” of zeros/ones in A.
For example, for A = [0, 1, 1, 0, 0, 1, 1] there are four blocks: [0], [1, 1], [0, 0], [1, 1], so the answer is 4.
The number of blocks is equal to one plus the number of indices i such that A_i \neq A_{i+1}.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 1
    for i in range(1, n):
        if a[i]%2 != a[i-1]%2: ans += 1
    print(ans)
2 Likes