M_H_M's blog

A Good Problem
By M_H_M, history, 10 years ago, In English

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.

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

»
10 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Are the numbers positive?

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it -23 Vote: I do not like it

UPD: it is also solvable with convex hull trick in O(n).

→ Reply
»
10 years ago, hide # |
← Rev. 9  
Vote: I like it -9 Vote: I do not like it

Example : A=> 1 3 2 5 3

Suffix [3,4) => 5

Answer => 5

Why you don't get Maximum the number??

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it -94 Vote: I do not like it

Come on M_H_M!

Please do not waste others' time with terrible problems.

It can be solved with O(n) !!!

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it +2 Vote: I do not like it

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).

→ Reply
»
10 years ago, hide # |
← Rev. 5  
Vote: I like it -25 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it +15 Vote: I do not like it

    1-It's not binary searchable.

    2-How do you check that there's some prefix that gives you 0 in O(1)?

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it -13 Vote: I do not like it

      Thank you.

      1. 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)

      2. 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).

      → Reply
»
10 years ago, hide # |
 
Vote: I like it +68 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it -11 Vote: I do not like it

    I cant understand what it is saying, can you implement that?

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

    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.

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← Rev. 6  
      Vote: I like it +23 Vote: I do not like it

      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.

      → Reply
»
10 years ago, hide # |
← Rev. 3  
Vote: I like it +24 Vote: I do not like it

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)

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it +32 Vote: I do not like it

    I think it is not solvable with a better time than N^2

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

    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

    → Reply
»
10 years ago, hide # |
 
Vote: I like it +53 Vote: I do not like it

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)

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

Such a NICE Problem! It was really FANTASTIC!

→ Reply