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.