This is a post describing my solution for 617B - Chocolate.
For this problem, the key is viewing the act of breaking the candy bar as a sequential process with a number of decisions at each stage. Once we know how many decisions there are at each stage, we can apply the rule of product and multiply these numbers to arrive at the total number of possible outcomes.
The sequential process proceeds as follows:
- Start at the left side of the candy bar
- Keep marching until we get between two nuts
- Make a break somewhere between these two nuts
- Go back to step 2
In step 3, we can make multiple decisions. If there are n zeros between the two nuts, then we can make a break so as to give n zeros to the left nut and 0 zeros to the right nut, or we can make a break so as to give n-1 zeros to the left nut and 1 zeros to the right nut, and so on. In total, we have n+1 decisions for this particular break.
To help visualize this process, consider the following diagram on the input sequence 10101:
We first consider nuts 1 and 2 and see that there is only one zero in between them. Hence we can make a total of 2 different breaks, as pictured by the two branches. After making this first break, we proceed to nuts 2 and 3. Once again, there is only a single zero between these two nuts; hence the number of breaks we can make here is 2. We get the total number of breaks by multiplying these numbers for a total of 2*2 = 4 possible breaks.
One edge case that is captured in my algorithm, but is nonetheless useful to consider are when there are leading and trailing zeros. Note here there is only one legal break we can make. For leading zeros, the only legal break point is before the first zero. For the trailing zeros, the only legal break point is after the last zero. This is because any other break would result in a piece of chocolate with zero nuts. As a preprocessing step, I simply stripped leading and trailing zeros, but one can equivalently keep them and simply include them in the product as multiplication by 1 leaves the result unchanged.
