bachmanity_insanity's blog

Kickstart Practice Round 2018
By bachmanity_insanity, history, 7 years ago, In English

Can someone explain me the approach for the problem:Sums of Sums Thanks:)

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

The caveats of the problem are

  • All numbers in the original array are positive

  • The final array is sorted

First, instead of getting sum[L, R] in the final sequence, let's get the value of

sum[1, R] - sum[1, L - 1] (this is sometimes called prefix-sums)

Now the problem is that we can't generate the numbers explicitly as there are lots of them, but we can do some two-pointer approach in the original array to count the sum of all subarrays that have sum <  = M and how many of them exist in linear time (after choosing M). The idea is to binary search for M. If we want to know sum[1, IDX] in the final array, we must find M such that quantityfinal_array( <  = M) <  = IDX (we get the sum with the method I will talk below and just add to it (M + 1) * (IDX - (quantityfinal_array( <  = M))))

Considering the original array, let's focus on a sum on the interval [L, R]. Let's iterate through the endpoint R to get our quantity of subarrays and the sum of them such that all are good (sum <  = M) and end in position R. If sum[L, R] <  = M, the sum of [L + 1, R], [L + 2, R], etc will also be good (all numbers in the original array are positive), so we can add to our quantity R - L + 1 and to the sum we add v[L] + 2 * v[L + 1] + 3 * v[L + 2], etc (how many times that numbers are added in a sequence ending in position R) and after that we increase R and do the same thing. If the sum is  > M we just increase L. We can get those sums in constant time by adding the appropriates values when increasing R or L (you can refer to my code for details).

→ Reply