OETW - EDITORIAL

cook98
easy
observations
oetw
prefix-sum
taran_1407

#1

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 :smiley:
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. :smiley:

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. :slight_smile:


#2

The following sample case was given for this problem:

INPUT

1
3
2 1 2

OUTPUT

4


And I totally understand why it is 4 for this test case. But I found solutions which got AC during the contest even after giving wrong answer for this particular test case. There are two solutions which I found faulty in this respect which got AC during the contest.


20307252 by hroarr in COOK98B (Output for this case: 5)

20314080 by daniyal1998 in COOK98B (Output for this case: 2)


It might be the case that many faulty solutions were submitted who got accepted during the contest in both Division 1 and Division 2. Or, it might be the case with other problems in this contest as well.

I believe that the test cases were very loose and weak for this problem.


I recently emailed this concern to bugs@codechef.com, as I thought it must be reported.


#3

I have a doubt.
Consider the given array
2 2 1 2 2 1 2 2 1 2 2 2 2 2 2
here the prefix sum of the largest subarray with 1st and last number 1 is 11.
but z=18 is reachable which is greater than 11 and even which seems to be an counterexample to above solution.
Could you please clarify if i am getting it right.


#4

Tester’s solution is incorrect!

1 5 2 2 1 2 1

Returns 7. The correct answer is 8.


#5

Here is the proof for S−min(C1,C2)

We observe that if we get 1 2 2 2 or 1 2 2 1 1 2 or 2 2 1 2 1 i.e. any subarray which is starting or with ending with 1 we can make every number till its sum.

Now, if we see in this 2 2 1 2 2 1 1 2 all possible numbers till prefix sum at 7 is possible. While after that it won’t be possible. Also we can consider that all numbers till suffix sum at 3 is possible. While before that it won’t be possible. Because of each 2 we won’t be able to make a number.

Hence, with other examples it can be shown that we need to know number of 2’s just before first occurrence of 1 either from left or right side whichever is optimal and subtract it from total sum.


#6

Actually while implementing the solution we need first check one thing ,whether the array is starting with 1 or ending with 1 .If the answer is “YES” we need to print the sum of the array straight forward.If the answer is “NO” we need compute the answer using the above method.Just be aware of otherwise you might get wrong answers while solving it.( although the editorialist mentioned this many people tend to forget this point)


#7

A short python solution.


#8

I can’t proof this but it got an AC.

if array has only twos:
ans= sum/2

else if array starts and ends with 2:
ans= sum-1

else
ans=sum

Here’s my solution.


#9

If C_1 and C_2 in S-min(C_1, C_2) are the number of consecutive $2$s on the left and on the right end respectively then this formula holds true even if there are no $1$s in the array (all the array elements are equal to 2).

All sub-array sums are in the range 1..S. If we only consider the set of prefix sums then for any X in that range either X or X+1 belongs to the set. If the array starts with 1 consider the set of sums of all sub-arrays that start from the second position. For any X from the range 1..S X is either equals to one of these sums or one of the prefix sums, so that the set of all sub-array sums fills the entire range. The same is true when the array ends with 1.

If our array contains a sub-array with sum s that starts or ends with 1 then the set of sums of all sub-arrays is guaranteed to contain the range 1..s. What is the largest sum sub-array that starts or ends with 1? One end of this sub-array is 1 that is closest to an array end, and the other - the opposite end of the array. Let C = min(C_1, C_2). Then the size of this sub-array is N - C. All sub-arrays of this size contain all the $1$s of the entire array and have the same sum S - 2C. Sub-array with a larger sum is of a larger size, it also contains all the $1$s of the entire array, its sum depends only on its size, which increases by 2 if the size increases by 1. So we have S - 2C consecutive values for sub-array sizes up to N-C following by C values in increments of 2 for sizes up to N (S - C total).


#10

Seems like you misunderstood my statement.

I meant, either starting with, or ending with. Both are not necessary. In your example, the largest sub-array starting or ending with 1 has sum 23. Only values 24 and 26 are unreachable.


#11

Thanks for reporting. @admin is already aware of this issue.


#12

okay.Got it.Thanks


#13

answer is 8 that’s true


#14

Then what action is taken with this respect ? @taran_1407 @admin


#15

I think we do not need to check this case specially. Though no harm mentioning :slight_smile:


#16

Well, i think we’ll have to wait for admin statement.


#17

update ur solution as-- if array has only twos: ans=sum/2


#18

for second line, for test case 2 2 1 2 2 output is 7 because 6 and 8 can not be made… but according to ur second point, ans=sum-1 so it would be 9-1=8 but ans is 7… i am getting confused


#19

exactly…


#20

i think ur approach is wrong…
actual answer will be sum-min(c1,c2) where c1 is no of 2’s before leftmost 1 and c2 is no of 2’s after rightmost 1