rhezo's blog

Interesting problem about Subarray sums. Help needed!
By rhezo, history, 8 years ago, In English

The problem is that we need to put sum of all individual sub arrays in an array, and sort the array. Then there are at most 20 queries of the form [L, R], we need to report the sum between the indices L and R in the sorted array.

Here is the link.

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

»
8 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

Maybe the following approach is fast enough. It's .

  1. Binary search value of the L-th element in the sorted array of size N·(N + 1) / 2. To check if some value is too big/small, you can use the two-pointers technique (with two pointers move over the given sequence of size N to count intervals with sum smaller than the fixed value).
  2. Binary search value of the R-th element in the sorted array of size N·(N + 1) / 2.
  3. Again with two pointers move over the given sequence of size N and sum up sums of intervals with sums in interval [v1, v2] where v1, v2 are values found with binary search.

Codechef should hire someone to check the statements before the contest (typos and other mistakes).

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What should I do in cases where the sum-array has repeated numbers?

    Example: [1, 1, 1, 1, 2, 2, 2, 3, 3] (obtained when the original array is [1, 1, 1, 1]). If L = 2 and R = 6, v1 will be 1 and v2 will be 2, so the third step would give as result the sum of every element whose value is in interval [1, 2], i.e. 10, while the correct result should be 7.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +9 Vote: I do not like it

      TL;DR
      Find c — the number of intervals smaller than v1. From the sum of sums in interval [v1, v2] you must subtract (L - 1 - c)·v1 because we shouldn't have summed L - 1 - c sums equal to v1. Do the same from the right for R. In case it isn't clear what to do, read much more detailed description below.

      First, let me give you a useful advice. To avoid copy-pasting or writing similar thing twice, at the begging you should change problem from
      - "find the sum of elements from L to R"
      into
      - "for given X find the sum of elements from 1 to X"
      and then print f(X = R) - f(X = L - 1). It's very standard trick and allows to avoid mistakes.

      Now, we are given some X and the task is to sum up smallest X sums. We binary search the value of the X-th smallest sum (as I described in the first post). Let v denote this value. With two pointers we can find the following values:

      • S — the sum of sums smaller than v
      • c — the number of sums smaller than v

      The answer is S + (X - c)·v. I will explain why. In the sorted array of size N·(N + 1) / 2 we summed up first c elements (smaller than v) and just after them there are some elements equal to v. We must add X - c of them (because we already summed first c but we need first X elements).

      → Reply