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.
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)
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..SX 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).
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.
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
âThank you for your detailed report. We apologize for the weak test data. After analyzing, we found that this does not disadvantage users who had correct answers too much, and hence we are keeping the contest rated. We will ensure that such issues donât crop up again.â
This is the reply that I got for my email.
Problem with super quick explanationâs latex:
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.
