I think it will become clear with an example.

Let's assume the given array is `a = [0 0 0 0 0]`

.

*"Let’s create an array *`cnt[]`

, where `cnt[i]`

equals 1, if the sum of elements from i-th to n-th equals `S/3`

and 0 — otherwise." -where `S`

is the sum of all the elements of the array `a`

. Constructing the `cnts`

array, we get

`a = [0 0 0 0 0]`

`cnts = [1 1 1 1 1]`

*"Now, to calculate the answer we have to find the sum *`cnt[j] + cnt[j+1] + ... + cnt[n]`

faster then O(n). There are a lot of required ways to do this, but the easiest one is to create a new additional array `sums[]`

where in j-th element will be `cnt[j] + cnt[j+1] + ... + cnt[n]`

"

`a = [0 0 0 0 0]`

`cnts = [1 1 1 1 1]`

`sums = [5 4 3 2 1]`

*"Thus, we receive very simple solution: for each prefix of initial array 1..i with the sum that equals we need to add to the answer sums[i+2]."*

We are required to break the given array into 3 pieces. If we are at the i-th element and the sum of elements from 0 to i is equal to `S/3`

then the segment from 0 to i is a valid **first piece** of the array. And for all the position j where `cnts[j]`

is 1, the segment from j to the end is a valid **third piece** of the array. Since we require a **second piece** of the array, **there must be a segment of non-zero length between these 2 segments**, which is why the "i+2" comes in. It ensures that the second segment is of length ≥ 1. Hence if you choose the given prefix 0 to i with sum `S/3`

as the first piece, then the number of ways to choose the third piece is equal to the number of positions ≥ i+2 where the `cnts[]`

value is 1. This is nothing but `sums[i+2]`

.

Getting back to the example, only 3 prefixes within acceptable range have sum `S/3`

marked with `|`

and their +2 positions marked with `^`

.

`a = [0 0 0 0 0]`

`cnts = [1 1 1 1 1]`

`sums = [5 4 3 2 1]`

`. |---^`

`. |---^`

`. |---^`

The answer is hence 3+2+1=6, and the actual 6 ways are

`[0 | 0 | 0 0 0]`

`[0 | 0 0 | 0 0]`

`[0 | 0 0 0 | 0]`

`[0 0 | 0 | 0 0]`

`[0 0 | 0 0 | 0]`

`[0 0 0 | 0 | 0]`

answered
**26 May '17, 05:06**

6★meooow ♦

7.1k●7●18

accept rate:
48%