If you got an AC then your solution is likely to be wrong as the tester’s solution is. 
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).
“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.
1 Like