PROBLEM LINK
Contributors
Author: Amit Pandey
Tester & Editorialist: Prateek Gupta
DIFFICULTY:
Medium
PREREQUISITES:
Number theory
PROBLEM:
Find any valid array of N integers having E contiguous subarrays with even sum and O contiguous subarrays having odd sum. In case, no such array exists, output “-1” (without quotes).
EXPLANATION
Solution for Subtask 1:
Since, the constraint of N is as small as 15, it can be easily solved by bit masking. It is a simple realization that each of the N integers will be either odd or of even parity and that is how the count of even sum and odd sum contiguous subarrays will be impacted. Having said that, we can place either an odd or an even integer in each of the N places. This gives rise to iterating over all sets of combinations and finding the valid one if it exists.
for ( mask = 0 to 2^n - 1 ) {
a[0] = 0
even_subarrays = odd_subarrays = 0
for ( j = 0 to n - 1 ) {
if ( bit j is set in mask ) a[j + 1] = 1
else a[j + 1] = 0
}
for ( j = 1 to n ) {
sum = 0
for ( k = j to n ) {
sum += a[k], sum %= 2
if ( sum ) odd_subarrays += 1
else even_subarrays += 1
}
}
if ( even_subarrays == E and odd_subarrays == O ) {
print(array, a)
exit
}
}
print("-1")
The overall complexity for the above approach is \mathcal{O}(N^2*2^N) which is exponential and hence too slow for the rest of the subtasks.
Solution for subtask 2 & 3:
The key to approach the optimized solution is to start from backwards.
Let us denote the prefixSum_i as the sum of first i integers of any valid array to be computed. Now, there are some important observations.
- If you somehow know the number of prefixSums having odd and even parity respectively, you can correspondingly create any valid array provided that total count of oddPrefixSums and evenPrefixSums is $N\ +\ 1$. For eg :- If you have 3 evenPrefixSums and 2 oddPrefixSums, you can create an array $[0,\ 0,\ 1,\ 0]$. The trick is to place an only $1$ after placing $evenPrefixSums\ -\ 1$ zeros. All the remaining prefixSums will obviously be of odd parity. Having said this, the following equation holds true.
- How to calculate the number of contiguous subarrays having odd parity? Since, $prefixSum_i\ -\ prefixSum_j$ contributes to sums of contiguous subarrays, both should be of different parity. Hence, number of contiguous subarrays having odd parity will indeed be $C(evenPrefixSums,\ 1)*C(oddPrefixSums,\ 1)$. This gives rise to another equation.
How to compute the number of evenPrefixSums and oddPrefixSums?
Approach 1
Looking at equation 2 which is of the form a*b\ =\ X, you can go ahead to compute the divisors of X which will satisfy a\ =\ i and b\ =\ X/i provided that X\ mod\ i\ =\ 0. If any such pair of (a,\ b) also satisfies the equation 1 of the form a\ +\ b\ =\ Y, we get a valid pair. Find the pseudo code below for the same.
LIM = square_root(odd)
for ( i = 1 to LIM ) {
if ( odd % i == 0 ) {
if ( i + odd/i == n + 1 ) {
odd_prefix_sums = i
even_prefix_sums = odd/i
}
}
}
Approach 2
Alternatively, you can form a quadratic equation and solve it to get the respective values. If you do not find any valid values, output “-1”.
Note
Depending upon your implementation, cases having E or O as 0 might be tricky.
For more details on the implementation of any subtasks, have a look at the tester’s solution. If you want to enjoy a good reading about other Number theory algorithms, feel free to visit this blog post.
COMPLEXITY
Overall time complexity for the above approach is \mathcal{O}(N) per each test case.
SOLUTIONS
Setter
Tester’s solution to Subtask 1
Tester’s solution to Subtask 2 & 3 - Approach 1
Tester’s solution to Subtask 2 & 3 - Approach 2
