COUNTP - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Kunj Rakesh Patel
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh

DIFFICULTY:

1065

PREREQUISITES:

None

PROBLEM:

Given an array A of length N, it is possible to partition it into two non-empty subsequences such that the product of their sums is odd?

EXPLANATION:

Suppose we were able to split A into two subsequences S_1 and S_2 satisfying the given condition.

Then, note that we want sum(S_1)\times sum(S_2) to be odd, which is only possible when sum(S_1) and sum(S_2) are both odd.
Further, S_1 and S_2 partition A, and so sum(S_1) + sum(S_2) = sum(A).

Since sum(S_1) and sum(S_2) must both be odd, sum(A) must be even.
So, if sum(A) is odd the answer is immediately “No”.
From now on, let’s consider sum(A) to be even.

If A contains only even numbers, then any subsequence also has even sum so splitting into two subsequences with odd sum is impossible.
On the other hand, if A contains an odd number, say x, then we can simply choose S_1 = \{x\} and S_2 to be all the other elements.

S_1 obviously has odd sum, and since sum(A) is even, S_2 also has odd sum and we’re done.

So, the answer is “Yes” if and only if sum(A) is even and A contains at least one odd number.

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()))
    print('Yes' if sum(a)%2 == 0 and sum(x for x in a if x%2 == 1) else 'No')
1 Like