### M_H_M's blog

By M_H_M, history, 6 years ago, 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

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 + a + .. + 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. Comments (40)
 » 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
 » 6 years ago, # | ← Rev. 2 →   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
 » 6 years ago, # | ← Rev. 9 →   Example : A=> 1 3 2 5 3Suffix [3,4) => 5Answer => 5Why you don't get Maximum the number??
•  » » For any Suffix !!! Maximum prefix of that suffix
 » 6 years ago, # | ← Rev. 2 →   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 wrongin case: 4 2 5 3 6just 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
•  » » » » » » » » » You are not allowed to give a test with n=100000; This causes segmentation fault! btw how did you check it???
•  » » » » » » » » » 6 years ago, # ^ | ← Rev. 4 →   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.
 » 6 years ago, # | ← Rev. 2 →   I think we can use the idea of prefix function. We wish to find array s,s,...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 ?
 » 6 years ago, # | ← Rev. 5 →   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)?
•  » » » 6 years ago, # ^ | ← Rev. 3 →   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/0311020It's actually really easy to implement, so don't be scared :)
•  » » I cant understand what it is saying, can you implement that?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   Here is my implementation for weights equal to one. UPD: The code is updated.
•  » » 6 years ago, # ^ | ← Rev. 2 →   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.
•  » » » 6 years ago, # ^ | ← Rev. 6 →   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: r[-1] = -1 r[j] = j+1 for all other j for j from 0 to n-1 update(j); print the average of [phi[q-2], phi[q-1]) 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.
 » 6 years ago, # | ← Rev. 3 →   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
•  » » 6 years ago, # ^ | ← Rev. 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 + a + .. + 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!