PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: DOlaBMOon
Tester: Hussain
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Prefix Sum
PROBLEM:
Given an array A consisting of only 1 and 2. Find number of unique values between 1 and 2*N which can represented as sum of a sub-array of array A.
Let us call a value X reachable, there exist a sub-array with sum X.
SUPER QUICK EXPLANATION
-
Find largest value $X$, such that $X$ is reachable while $X+1$ is not reachable, then all values up to $X$ and values $V$ which satisfy $X < V \leq S$ and $X \equiv V \pmod{2}$ are reachable, where $S$ is sum of array.
EXPLANATION
This problem have very simple implementation, if you get the intuition. So, Iâll be mostly focusing on idea and examples, Implementation can be referred from solutions.
Firstly, Note that to reach an odd value, we need at least one occurrence of digit 1. Easy enough, right? So, If array A doesnât contain digit 1 at all, we know, all even values are reachable.
Consider following examples
Array 1 2 2 2 2
We can manually see that all values from [1,9] is reachable.
Array 2 2 1 2 2
Values from [1,5] and 7 and 9 is reachable, while Sum 6 and 8 are not reachable.
Now, consider array 2 1 2 2 2
All values from [1,9] except 8 is reachable.
What do we learn from these examples?? We can see, that there is always an upper limit X up to which all values are reachable, while only values above X which have same parity as X are reachable.
Time for a general statement 
Formally, Once we consider a sub-array with sum which includes both leftmost as well as rightmost occurrence of digit 1, Parity of this sum, i.e. X cannot change, so, values V > X, having different parity with X, can never be reachable.
Now that we have proved that by the Maximum value, we can calculate the answer easily, we now try to calculate this Maximum value.
For this, consider another example of format 1,2,2,2\dotsc having N elements, prove that all values from [1, 2*N-1] is reachable.
Proof can be found below.
Click to view
For Odd values, we can include the 1 and get remaining sum using 2s. Even values can be obtained by excluding 1. But value 2*N can never be reached as sum of array is 2*N-1
So, we now know that by selecting a sub-array beginning or ending with one, we can reach all values up to sum of sub-array. So, The upper bound is actually the maximum sum of sub-array which either start or end with 1.
Also, The values above X sum having same parity as X can be reached by including remaining 2s.
This is it. Author checks for every position of 1 in array A, the largest sub-array sum either starting or ending at 1 using prefix sum array, while it suffices to check only sub-arrays [L, N] and [1,R] where L and R correspond to leftmost and rightmost position of 1 respectively, take the maximum of both.
Thatâs all, guys. Just implement it when you get the idea and Thatâs it.
Need another hint to calculate answer when X is known? see below.
Click to view
Answer is X+(S-X)/2. Still didnât get how?
Click to view
X values in range [1,X] are reachable and (S-X)/2 values in range [X+1,S] are reachable.
Also, using same observation, answer can also be calculated as S-min(C1, C2), where S is sum of array, C1 is Number of 2s before leftmost 1 and C2 is number of 2s after rightmost 1.
Can you prove it how?? This is an exercise for you.
AUTHORâS AND TESTERâS SOLUTIONS:
Setterâs solution
Testerâs solution
Editorialistâs solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 