PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have a binary array A of even length. In one move you can choose two adjacent elements of the array, add their difference to your score, and delete both from the array.
What’s the maximum score you can attain?
EXPLANATION:
Observe that |A_i - A_{i+1}| equals 0 if A_i = A_{i+1}, and 1 otherwise.
We want to maximize our score, so clearly it’s best to choose A_i \neq A_{i+1} as much as possible, i.e, a 0 and a 1.
Suppose A has X zeros and Y = N-X ones.
Then, observe that the best we can do is a score of \min(X, Y); since each move that increases our score must delete one 0 and one 1 from A.
It’s not too hard to see that this score is also attainable: as long as A contains both zeros and ones, there will be a zero adjacent to a one so we can choose them.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
zeros = a.count(0)
print(min(zeros, n - zeros))