Hello
Consider Array A. For any suffix of A compute the prefix with maximum average.
Example : A => 1 3 2 5 3
Suffix [2, 5) => 2 5 3
Answer => 3.5
Is there a better solution than O(N ^ 2) ??
UPD
IMAN_GH's comment :
Haghani solved the problem and here we have his solution :
sum[i] = a[0] + a[1] + .. + a[i — 1]
for any i consider point (i, sum[i])
if answer for suffix i equals j then (sum[j] — sum[i]) / (j — i) is maximum in all j > i.
it's solution is somthing like upper hull of some points. it solves by using stack with insert points in the hull and updating it.
if we insert points from right to left then answer for suffix i equals to the second point in the upper hull after adding point i.
Are the numbers positive?
Do U have any solution for positive ??
you can add abs(min of Array A) to all elements and compute the answer
UPD: it is also solvable with convex hull trick in O(n).
explain more
we need a data structure that can: 1- add a,2a,3a,4a,.. to segment[l,r] 2- give maximum value in segment[l,r] we can use sqrt decompose to solve it
Example : A=> 1 3 2 5 3
Suffix [3,4) => 5
Answer => 5
Why you don't get Maximum the number??
For any Suffix !!! Maximum prefix of that suffix
Come on M_H_M!
Please do not waste others' time with terrible problems.
It can be solved with O(n) !!!
explain more
It can be solved with a simple dp .
I don't think so...
So I have to repeat that word again: "explain more" :D
Please see this.
you are wrong
in case: 4 2 5 3 6
just a bad bluff!
Please explain more!
For i=2 it's better to choose 2,5,3,6 so you will get 4 instead of 3.5
Sorry I had a mistake in implementation.
Now it is fixed.
Thanks to puss_in_boots.
you are wrong in case: n=100000; for(int i=0;i<n;i++) a[i]=-30*i+1;
practice more!
You are not allowed to give a test with n=100000;
This causes segmentation fault!
btw how did you check it???
UPD2: It is not O(n2). It seems it is correct.
So we get the result that M_H_M was saying a bluff and judged too early.
It was a bad bluff
Now who was right? And who said a bluff?
You are wrong and it is solvable in O(n).
You can't say such a thing does not exist just because you don't know anything about it!
Nobody said there is no solution But D.Majid said it is very easy while he can't prove the solution.
Of course I can prove that, but if you look carefully, then you can see puss_in_boots has proved it and I do not want to repeat sth again.
I think we can use the idea of prefix function. We wish to find array s[1],s[2],...s[n] where s[i] denotes length of prefix starting at a[i] with maximum average. Now when we want to find s[i]. We look to a[i] and this our initial prefix for s[i]. If s[i+1] is bigger than our current average then we jump to i + s[i+1] index and continue in the same way. Obviously, it is better than O(n^2) in average, but is there test case where it would take O(n^2) worst case? I can't prove that it is linear time. UPD. Oh, it is obvious O(N):). The point is that you cannot jump over some s[i] more than one time. So it O(N+N) = O(N).
Can you prove the fact ?
Consider suffix starting at i. Suppose that we have found the maximal average value "Mean". Then:
Mean * (j — i + 1) >= a[i] + a[i+1] + ... + a[j] or sum(a[k] — mean) <= 0 for i <= k <= j.
So if there is a prefix whose sum is > 0, we increase Mean, all < 0 we decrease Mean, "=" happens when it exists. We can use binary search to find Mean and it is O(nlogn). There is a linear time algorithm for it, but I do not remember.
1-It's not binary searchable.
2-How do you check that there's some prefix that gives you 0 in O(1)?
Thank you.
You are right. I have just edited it a bit, now is it binary searchable now? If not, can you tell me the reason? (I don't know really)
Yes it is O(n), so the total is O(nlogn). If it is correct, even not as good as O(1), it is better than O(n^2).
You can find an O(n) algorithm here: http://arxiv.org/abs/cs/0311020
It's actually really easy to implement, so don't be scared :)
I cant understand what it is saying, can you implement that?
Here is my implementation for weights equal to one. UPD: The code is updated.
Actually the article gives online solution (we can add elements one by one to the end of the array) to find the segment with maximum density, but there are nothing there about finding maximum density suffixes of each prefix (they are finding ij not i * j). Also they are considering the general case when each value has also a weight and we have the constraints to the minimal and maximal sum of weights in answer.
It's true they talk about finding ij not i * j, but in our specific case wouldn't it be simple to modify the algorithm to print the correct i? Something like:
We don't even need function lbest() at all in this case.
Edit: I'm being hunted by WAs even in cf comments Edit 2: also, this is equivalent to the solution above, as phi is basically i, i+s[i], i+s[i]+s[i+s[i]], etc. But it was given without any proof, so putting it in this way should make it more obvious why it is correct.
What if it was (a[i]*a[i+k-1]+a[i+1]*a[i+k-2]+...+a[i+(k-1)/2]*a[i+k/2])/k ? I don't think that it would be better than O(N*N)
I think it is not solvable with a better time than N^2
it is more interesting to find k for any i such that :
(a[i — k] * a[i + k] + a[i — k + 1] * a[i + k — 1] + ... + a[i]) / (2k + 1) is maximum
Haghani solved the problem and here we have his solution :
sum[i] = a[0] + a[1] + .. + a[i-1]
for any i consider point (i, sum[i])
if answer for suffix i equals j then (sum[j]-sum[i]) / (j-i) is maximum in all j > i.
it's solution is somthing like upper hull of some points. it solves by using stack with insert points in the hull and updating it.
if we insert points from right to left then answer for suffix i equals to the second point in the upper hull after adding point i.
so problem solved O(N)
Such a NICE Problem! It was really FANTASTIC!