Since there’s a lot of discussion on this problem, I thought I’d share my technique:
Problem pages:
Div1 contest
Div2 contest
Practice
Problem statement:
Find the number of distinct sums of contiguous portions of a given array of 1 s and 2 s.
Analysis:
Probably like most people I thought briefly about summing all combinations, maybe with an accumulated array so it was just a subtraction each time. But the input array bounds seemed(?) too high for that. Looking at the boundary cases though, clearly we can make the array sum, so I coded up the two boundary cases - found using the sum - of all 1 s and all 2 s, which each allow only n sums. Then I realized (first insight) if we have a 2 on both ends of a mixed array we can’t make one less than the sum. In fact we can peel back the array to remove the shorter “tail” of 2 s and know that we have that many possible sums at the top end that we couldn’t make.
So what about when there is a 1 at one end of the array? This is the second insight, more important but enabled by the first one. If we look at the partial sums we can make without that 1, but including its neighbour, we form a sequence that goes up to the sum of the reduced array. And in that sequence, the biggest jump in values is only 2 - that is, if say 41 is somewhere in the middle of that sequence, then either 42 or 43 is next. Now if you look at the sums including the end 1 we were previously disregarding, that will be the same values shifted by 1, so will fill all the gaps in the previous sequence. So whenever there is a 1 at one end of the sequence, all sums are possible up to the sum of the sequence.
In case this “second insight” isn’t clear, here’s a practical example of a sequence with a 1 starting:
1 2 2 1 1 2 1 2 2 2
Partial sums starting from the second element (excluding the edge 1):
2 4 5 6 8 9 11 13 15
Partial sums starting from the 1:
1 3 5 6 7 9 10 12 14 16
and obviously the second set is each time one bigger (plus the leading 1), giving full coverage of all values from 1 to the sum.
Combining these two insights: find the shorter tail of twos, and the length of that will tell you how many values (to the sequence sum) you can’t make. All other values are possible.