PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic programming
PROBLEM:
You’re given an array A.
You can repeatedly do the following:
- Choose an index i such that A_i and A_{i+1} have the same parity.
Remove these two elements and insert A_i + A_{i+1} in their place.
Count the number of arrays reachable by repeating this operation several times.
EXPLANATION:
First, observe that if A_i and A_{i+1} have the same parity, then A_i + A_{i+1} must be even.
Thus, our operations can only insert even elements into the array.
This means that any odd elements in the final array, must have been present in the original array as well.
Further, since we’re merging adjacent elements, at any point of time the elements of the current array will represent sums of subarrays of the original array; such that these subarrays partition the original array.
Formally, if we perform merges to reach an array B of length M, then there will exist M pairs (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) such that:
- 1 = l_1 \le r_1 \lt l_2 \le r_2 \lt\ldots\lt l_M \le r_M = N
- l_i = r_{i-1} + 1 for each 2 \le i \le M
- B_i = A_{l_i} + \ldots + A_{r_i} for each i.
Now, since all the elements of A are positive, any reachable array B will correspond uniquely to a partition of A into subarrays.
Thus, counting reachable arrays is equivalent to counting valid partitions of A.
Let’s now try to count valid partitions.
For that, we need to understand when a subarray A[l, r] can appear as part of a partition at all, i.e. when it’s possible to merge all its elements into a single value.
First, if all the elements of A are even then it’s trivially possible; so we assume there are some odd values in there.
If the number of odd values is itself odd, then it’s not possible to merge into a single element (since, as noted at the start, we cannot create any new odd elements.)
The only exception to this is if l = r i.e. the subarray consists of a single odd element; which is allowed because no merges are needed.
Finally, if the subarray contains an even number of odd elements, merging into a single element is possible if and only if all the odd elements can be formed into adjacent pairs.
More formally, let x_1, x_2, \ldots, x_{2k} be the positions of the odd elements in [l, r], from left to right.
Then, observe that we must have:
- x_2 = x_1 + 1
- x_4 = x_3 + 1
\vdots - x_{2k} = x_{2k-1} + 1
This is because the first element is forced to merge with the second since it has no other choice; then that forces the third and fourth to merge, and so on.
It’s easy to see that this condition is necessary and sufficient.
Thus, [l, r] can be merged to a single element if and only if:
- There are an even number of odd elements in [l, r], and these odd elements can be all matched into adjacent pairs; or
- l = r and A_l is odd, i.e. the subarray is a singleton odd element.
We can use the above criterion to do our counting.
Define dp(i, p) to be the number of ways to split the first i elements of the array into subarrays, such that the final subarray has even/odd sum (represented by p=0/1 respectively.)
The answer is dp(N, 0) + dp(N, 1) since that accounts for partitioning the entire array.
As for transitions, we separate the cases of even and odd elements.
First, suppose A_i is even.
Then,
- dp(i, 1) = 0 always - the last subarray must have even value since it contains an even element.
- For dp(i, 0), observe that there are two choices: either keep A_i as a singleton, or merge it with the subarray till index i-1.
- The first option gives us free rein till index i-1, so there are dp(i-1, 0) + dp(i-1, 1) choices.
- The second option forces the previous subarray to also have even sum; and hence only dp(i-1, 0) ways.
- Thus, we have dp(i, 0) = 2dp(i-1, 0) + dp(i-1, 1).
Next, suppose A_i is odd.
By similar reasoning,
- dp(i, 1) = dp(i-1, 0) + dp(i-1, 1), since for an odd sum we are forced to keep A_i alone and then the previous index can do anything.
- If A_{i-1} is even, then dp(i, 0) = 0 since we have no option of merging A_i with another element (which is necessary to obtain an even sum.)
- If A_{i-1} is odd, then we can merge A_{i} and A_{i-1} into a single even element and then perform transitions with them instead.
The logic is exactly the same as the even case, and so we obtain
dp(i, 0) = 2dp(i-2, 0) + dp(i-2, 1)
This gives a solution in \mathcal{O}(N) time so we’re done.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
mod = 998244353
for _ in range(int(input())):
n = int(input())
a = [0] + list(map(int, input().split()))
dp = [[0, 0] for i in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
if a[i]%2 == 0:
dp[i][0] = (2*dp[i-1][0] + dp[i-1][1]) % mod
if i == 1: dp[i][0] -= dp[i-1][0]
else:
dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % mod
if a[i-1]%2 == 1:
dp[i][0] = (2*dp[i-2][0] + dp[i-2][1]) % mod
if i == 2: dp[i][0] -= dp[i-2][0]
print((dp[n][0] + dp[n][1]) % mod)