6

This is a question from the 2017 Google APAC. Problem D: Sum of Sum

Alice presented her friend Bob with an array of N positive integers, indexed from 1 to N. She challenged Bob with many queries of the form "what is the sum of the numbers between these two indexes?" But Bob was able to solve the problem too easily.Alice took her array and found all N*(N+1)/2 non-empty subarrays of it. She found the sum of each subarray, and then sorted those values (in nondecreasing order) to create a new array, indexed from 1 to N*(N+1)/2. For example, for an initial array [2, 3, 2], Alice would generate the subarrays [2], [3], [2], [2, 3], [3, 2], and [2, 3, 2] (note that [2, 2], for example, is NOT a subarray). Then she'd take the sums -- 2, 3, 2, 5, 5, 7 -- and sort them to get a new array of [2, 2, 3, 5, 5, 7].Alice has given the initial array to Bob, along with Q queries of the form "what is the sum of the numbers from index Li to Ri, inclusive, in the new array?" Now Bob's in trouble! Can you help him out?

The straight forward solution is too inefficient even in c++ for large data sets. Is there a more efficient way to solve this?

Currently i'm going through this for loop to construct the final array:

    multiset<int> sums;
    long long int temp = 0;
    for (long long int len = 1; len <= n; ++len)
    {
        for (int start = 0; start+len <= n; ++start)
        {
            temp = 0;
            for (int i = 0; i < len; ++i)
            {
                temp += arr[start + i]; //arr stores the original array of n digits
            }
            sums.insert(temp);
        }
    }

P.S: Is my current implementation O(n^5)? My mistake, I can see how its O(n^3) now. Thank you Edit: Answers so far have been helpful but with large datasets involving n = 200000 items, it appears that any solution that pre calculates the entire array of subarrays is too expensive. All the submitted solutions don't appear to calculate the entire array of subarrays

7
  • 2
    how do you come up with O(n^5) ? I see only 3 loops Jul 1, 2016 at 20:19
  • 1
    I don't know what do you mean by O(n^5), but simple solution will run in O(T*Q*N^2*logN). Jul 1, 2016 at 20:47
  • 3
    According to your code. Simple optimization is that you can precalculate prefix sums and calculate subarray sum in O(1). Jul 1, 2016 at 20:50
  • 3
    The problem has many important properties: First, N <= 200000, Q <= 20, and second each element in the initial array <= 100. This means that the maximum sum that you can get is 2 x 10 ^ 7. This number is not that big so you can have an array of this size in your program I think somehow you should use this. Jul 1, 2016 at 22:01
  • 1
    So what is your real question? If Is there a more efficient way to solve this? then the answer is clearly yes, because some people solved it. If it is Is my current implementation O(n^5)? then it is no. You have 3 loops it is O(n^3) Jul 2, 2016 at 1:13

4 Answers 4

3

As noted in the comments, your solution is O(N^3), computed as O(N^2) times a O(N) sum and an insertion in multiset (which you can ignore compared to O(N), see bottom of this answer).

But swap your two first loops, you're doing the exact same N*(N+1)/2 sums and insertions:

for (int start = 0; start < n; ++start)
{
    for (long long int len = 1; start + len <= n; ++len)
    {
        temp = 0;
        for (int i = 0; i < len; ++i)
        {
            temp += arr[start + i]; //arr stores the original array of n digits
        }
        sums.insert(temp);
    }
}

Now if you look at your temp sums it seems obvious you're doing redundant work. Sum from start + 1 to start + 1, then from start + 1 to start + 2, then from start + 1 to start + 3, etc. For each new len, the sum you're computing is the one for the previous value of len, plus one item. Hence you can remove this inner loop:

for (int start = 0; start < n; ++start)
{
    temp = 0;
    for (long long int len = 1; start + len <= n; ++len)
    {
        temp += arr[start + len]; //arr stores the original array of n digits
        sums.insert(temp);
    }
}

So in N*(N+1)/2 you generated the set of values. Of course, using a multiset you hide the data sorting, but insertion in general costs log(sums.size()).

Sorting separately, since sorting a set of size S should take S * log(S), would cost N*(N+1)/2 * log ( N*(N+1)/2 ) which is (just) less than N*(N+1) * log((N+1)/sqrt(2)).

Note that since you have positive integers, each set of len integers you generate with the inner loop is already sorted, so maybe you can use them to do something smart to speed up sorting. Which is also what multiset does according to cplusplus.com:

If N elements are inserted, Nlog(size+N) in general, but linear in size+N if the elements are already sorted according to the same ordering criterion used by the container.

3
  • An O(n^2 log n) solution is still very likely too slow for n = 200 000. I am guessing that O(n log X) is expected, where X is either n or the sum of all numbers in the new array, probably the latter.
    – IVlad
    Jul 2, 2016 at 12:04
  • @IVlad well that's the fastest way to generate the whole sorted array: N^2/2 plus some sorting. Faster solutions must not generate it.
    – Cimbali
    Jul 2, 2016 at 13:09
  • There exist a solution without generating subarrays. Many people have solved the original question in O(n logn) but I am not getting it
    – Mike
    Jul 2, 2016 at 14:52
1

Doing a little search I have found this, I hope it will be useful

https://www.quora.com/How-can-problem-D-Sums-of-sums-from-Round-E-of-the-Google-APAC-Test-2016-be-solved-for-the-large-dataset

1
  • Oh that is very embarrassing. Should have searched better... Thank You
    – AnkithD
    Jul 5, 2016 at 13:37
0

The most concise and efficient way I can think of is this:

std::vector<int> in{ 2, 3, 2 };
std::vector<int> out(in.size()*(in.size()+1)/2);

auto out_it = out.begin();
for (size_t i = 0; i < in.size() ; ++i) {
    out_it=std::partial_sum(in.begin()+i, in.end(), out_it);
}
std::sort(out.begin(), out.end());

Beside complexity considerations (This solution is - I believe - O(n^2 * log(n)) as you are sorting an array with O(n^2) entries), you should avoid dynamic memory allocations and pointer chasing like the plague (which both are an inherent part of std::multi_set).

2
  • There is absolutely no way you will be able to declare out of that size.
    – IVlad
    Jul 2, 2016 at 18:36
  • @IVlad: You are right. I wasn't aware about the 200,000 element requirement (all other proposed solutions have the same problem). I'll revise my answer as soon as I've time.
    – MikeMB
    Jul 2, 2016 at 23:09
0

My Python 3 version is below.

I did not test all test cases, but this would be just an idea to achieve:

from functools import reduce
import itertools

stuff = [2,3,2]
temp = []
for L in range(1, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        if len(subset) > 1:
            if all(subset[0] == x for x in subset):
                continue
        print(subset)
        temp.append(reduce(lambda x,y: x+y, subset))

temp = sorted(temp)
print(temp)
print("all sum : ", reduce(lambda x,y: x+y, temp))
1
  • Welcome to Stack Overflow. In future, please separate your written answer and explanation, from any code samples that you supply. Jul 25, 2018 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.