KDCT02 - Editorial







In simple terms, the question can be rewritten as:

Consider an array, A, of length n. We can split A into contiguous segments and store them as another array, B. We consider the value of such a segment in some array B to be (sum of all numbers in segment) * (length of segment), and we consider the total value of some array to be the sum of the values for all segments in that array.


The simplest solution is the recursive brute force approach. But the required complexity is atleast O(n^2), so this approach doesn’t pass all test cases. On examining the pattern carefully, we can arrive at the following recurrence relation:

T[n] = T[n-1] + 2^(n-2)*(a[n])               // T[n-1] forms 2^(n-2) subsets
 + T[n-2] + 2^(n-3)*(a[n-1] + a[n]) * 2
 + T[n-3] + 2^(n-4)*(a[n-2] + a[n-1] + a[n]) * 3
 + ...
 + T[1]   + 2^0*(a[2] + a[3] + ... + a[n]) * (n-1)
 + T[0]   + (a[1] + a[2] + ... + a[n])*(n)

where T[0] = 0

Now, to simplify the addition, let us use an array S where S[n] is the presum of a[0] to a[n]. So any sum from a[i] to a[j] is S[j] - S[i-1].

Now the solution become something like:

T[n] = 2*T[n-1] + 2^(n-1)*S[n] + (2^(n-1)-1)*a[n]
 - (2^(n-2)*S[n-1] + 2^(n-3)*S[n-2] + ... + S[1])

Thus, the required sum can be calculated in O(n^2) time.