M_H_M's blog

A Good Problem
By M_H_M, history, 9 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

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

Are the numbers positive?

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

    Do U have any solution for positive ??

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

    you can add abs(min of Array A) to all elements and compute the answer

    → Reply
»
9 years ago, # |
← 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
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    explain more

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -24 Vote: I do not like it

      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

      → Reply
»
9 years ago, # |
← 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
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    For any Suffix !!! Maximum prefix of that suffix

    → Reply
»
9 years ago, # |
← 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
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    explain more

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -95 Vote: I do not like it

      It can be solved with a simple dp .

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        I don't think so...

        So I have to repeat that word again: "explain more" :D

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it -55 Vote: I do not like it

          Please see this.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +30 Vote: I do not like it

            you are wrong

            in case: 4 2 5 3 6

            just a bad bluff!

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it -25 Vote: I do not like it

              Please explain more!

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

                For i=2 it's better to choose 2,5,3,6 so you will get 4 instead of 3.5

                → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it -14 Vote: I do not like it

              Sorry I had a mistake in implementation.
              Now it is fixed.
              Thanks to puss_in_boots.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it +26 Vote: I do not like it

                you are wrong in case: n=100000; for(int i=0;i<n;i++) a[i]=-30*i+1;

                practice more!

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 years ago, # ^ |
                    Vote: I like it +26 Vote: I do not like it

                  You are not allowed to give a test with n=100000;
                  This causes segmentation fault!
                  btw how did you check it???

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 years ago, # ^ |
                  ← Rev. 4   Vote: I like it +47 Vote: I do not like it

                  UPD2: It is not O(n2). It seems it is correct.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 years ago, # ^ |
                    Vote: I like it +22 Vote: I do not like it

                  So we get the result that M_H_M was saying a bluff and judged too early.

                  → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        It was a bad bluff

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          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!

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +13 Vote: I do not like it

            Nobody said there is no solution But D.Majid said it is very easy while he can't prove the solution.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it -12 Vote: I do not like it

              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.

              → Reply
»
9 years ago, # |
← 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
»
9 years ago, # |
← 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
  • »
    »
    9 years ago, # ^ |
      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
    • »
      »
      »
      9 years ago, # ^ |
      ← 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
»
9 years ago, # |
  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
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

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

      Here is my implementation for weights equal to one. UPD: The code is updated.

      → Reply
  • »
    »
    9 years ago, # ^ |
    ← 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
    • »
      »
      »
      9 years ago, # ^ |
      ← 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
»
9 years ago, # |
← 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
  • »
    »
    9 years ago, # ^ |
      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
  • »
    »
    9 years ago, # ^ |
    ← 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
»
9 years ago, # |
  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
»
9 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Such a NICE Problem! It was really FANTASTIC!

→ Reply