ALOST - Editorial

PROBLEM LINK

Practice

Contest

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.
  • evenPrefixSums\ +\ oddPrefixSums\ =\ N\ +\ 1
  • 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.
  • evenPrefixSums\ *\ oddPrefixSums\ =\ O
Now, you have two equations and two unknown variables, therefore you can compute the values for evenPrefixSums and oddPrefixSums which will in turn give you the valid array as discussed.

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

1 Like

In the array [0, 0, 1, 0] aren’t there only 2 evenPrefixSums? And for an array of N numbers, how can the sum of EvenPrefixSums and OddPrefixSums be N+1? Did I miss something?

2 Likes

I too have same doubt :confused:

With some simulation i was able to find out that for the array of length N,there are only ceil(N/2)+1 valid even-odd pairs which were generated by a certain harmonic progression.

e.g. for n=5
e=15 o=0 ans={2,2,2,2,2},
e=10 o=5 ans={1,2,2,2,2},
e=7 o=8 ans={2,1,2,2,2},
e=6 o=9 ans={2,2,1,2,2}

link to my solution : https://www.codechef.com/viewsolution/10209246

3 Likes

@rishivikram The empty array is also considered for prefix sums.

Consider the contiguous array from 1 to i. The sum would be prefix(i) - prefix(0).

3 Likes

Hi,

Shouldn’t C(N + 1, evenPrefixSums) ∗ C(N + 1, oddPrefixSums) actually be
C(evenPrefixSums, 1) * C(oddPrefixSums, 1) or am I missing something?

1 Like

Yeah, thanks for reporting this. I have updated it. :slight_smile:

Empty array has 0 as it’s prefixSum i.e evenPrefixSum.

1 Like

Shouldn’t “evenPrefixSums ∗ oddPrefixSums = E” actually be “evenPrefixSums ∗ oddPrefixSums = O” since we are calculating the number of contiguous subarrays having “odd parity” or is it that I am misunderstanding it?

No, you are right. @Prateek, update it.

Thanks for reporting. Updated! :slight_smile: