6

Given an array of N positive integers. It can have n*(n+1)/2 sub-arrays including single element sub-arrays. Each sub-array has a sum S. Find S's for all sub-arrays is obviously O(n^2) as number of sub-arrays are O(n^2). Many sums S's may be repeated also. Is there any way to find count of all distinct sum (not the exact values of sums but only count) in O(n logn).

I tried an approach but stuck on the way. I iterated the array from index 1 to n.
Say a[i] is the given array. For each index i, a[i] will add to all the sums in which a[i-1] is involved and will include itself also as individual element. But duplicate will emerge if among sums in which a[i-1] is involved, the difference of two sums is a[i]. I mean that, say sums Sp and Sq end up at a[i-1] and difference of both is a[i]. Then Sp + a[i] equals Sq, giving Sq as a duplicate.

Say C[i] is count of the distinct sums in which end up at a[i].
So C[i] = C[i-1] + 1 - numbers of pairs of sums in which a[i-1] is involved whose difference is a[i].

But problem is to find the part of number of pairs in O(log n). Please give me some hint about this or if I am on wrong way and completely different approach is required problem point that out.

Improve this question
14
  • Well, it's an interesting problem. Everything I'm coming up with potentially requires considering all pairs of input elements, which is O(n^2). My gut says it's impossible. Commented Jul 6, 2013 at 21:50
  • I have been assured by one who gave me the problem that O(n logn) exists. I spent whole day thinking. Commented Jul 6, 2013 at 21:55
  • If you're still stuck tomorrow, ask him for a timeable demo, so you know he's not messing with you. Commented Jul 6, 2013 at 21:58
  • 4
    @all This is an active programming contest question. Please do not answer this. codechef.com/JULY13/problems/FARASA Commented Jul 7, 2013 at 4:48
  • 21
    Flaggers: We are aware that this is an ongoing Code Chef challenge. While this question may violate the spirit of the challenge, it does not violate the rules of Stack Overflow and does not warrant deletion. Please do not keep flagging it for deletion. Commented Jul 7, 2013 at 16:49

2 Answers 2

Reset to default
10

When S is not too large, we can count the distinct sums with one (fast) polynomial multiplication. When S is larger, N is hopefully small enough to use a quadratic algorithm.

Let x_1, x_2, ..., x_n be the array elements. Let y_0 = 0 and y_i = x_1 + x_2 + ... + x_i. Let P(z) = z^{y_0} + z^{y_1} + ... + z^{y_n}. Compute the product of polynomials P(z) * P(z^{-1}); the coefficient of z^k with k > 0 is nonzero if and only if k is a sub-array sum, so we just have to read off the number of nonzero coefficients of positive powers. The powers of z, moreover, range from -S to S, so the multiplication takes time on the order of S log S.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

This answer has been up long enough that it would be unfair to remove it now. Please don't vandalize it.
@David Few people are trying hard to get problem removed but moderators are ignoring them. Its one of the decisive problem of the contest. I am not accepting it to not give anyone hint of it. Can you please delete the solution now and re-post after contest is over. I will mark it accepted thereafter.
@user2011120: We're not ignoring them - you can see the comment above. We're just refusing them. Neither David nor others are obligated to remove their answers, nor are we to remove your question. You will have to take responsibility for your own actions; do not try to eschew this responsibility onto others. That is just selfish and unfair.
After knowing that its live competition question. My responsibility becomes to get it removed to keep spirit of competition. I tried everything to remove it. Since deletion is not under my control. So what most I can do is to request the replier.
"Compute the product of polynomials P(z) * P(z^{-1})". Well, I'm a little confused, but aren't there N elements in P()? Computing the product would be N^2 right?
|
0

You can look at the sub-arrays as a kind of tree. In the sense that subarray [0,3] can be divided to [0,1] and [2,3].

So build up a tree, where nodes are defined by length of the subarray and it's staring offset in the original array, and whenever you compute a subarray, store the result in this tree.

When computing a sub-array, you can check this tree for existing pre-computed values.

Also, when dividing, parts of the array can be computed on different CPU cores, if that matters.

This solution assumes that you don't need all values at once, rather ad-hoc. For the former, there could be some smarter solution.

Also, I assume that we're talking about counts of elements in 10000's and more. Otherwise, such work is a nice excercise but has not much of a practical value.

Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.