Hoyda's blog

Problem: Maximal Average on Array
By Hoyda, history, 7 years ago, In English

Problem: You are given an aray of N elements(N<1e6). You have to find maximal average of some continuous part of array. Minumum length of part=A, Maximum length =B (A,B<N).

Example: A=2,B=4,array={1,-3,6,2,5} Answer: 4.333

How to solve this problem?

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

»
7 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Use binary search on answer. We want to know if the answer is more than x. Subtract x from all elements. Now we want to find a segment with length from A to B and a positive sum. Can you do it?

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

    Actually, it took me a moment thinking about what you said this is a good idea for the check method in the binary search. If I got it right when you find a segment of length From A to B with positive-sum this means that we can obtain a better answer.

    Also, khadaev do you think we can optimize the part where we look for the segment of length from A to B using prefix sum (calculated once in the beginning)? Or do you have any idea about it?

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

      We need to find max(pi + a, ..., pi + b) for all i where pi are prefix sums. Easy way: use segment tree. Faster way: use queue with a maximum.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Binary search on answer. You will need to check if average of any subarray >= A. Then just subtract A from each value of the array and the problem reduces to — check if sum of any subarray >= 0. That can be done using DP. Time complexity is O(N*logA). There might be better solutions than this one.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Run a binary search for an answer. So, now the problem is how to check is there a subarray of a length from that interval with average no less than x. Using the array of the partial sums si = a1 + a2 + ... + ai, s0 = 0, average of interval (l, r) is equal to . So you have to check is there a pair 0 ≤ l < r ≤ n such that . Then sr - sl ≥ x * (r - l). sr - x * r ≥ sl - x * l. Denote ti = si - x * i, then our condition turns to tr ≥ tl. Iterate through r and then you need to check is there a l: r - B ≤ l ≤  r - A that tl ≤ tr. So you have to take the minimum from the segment (r - B, r - A) from the array t. It can be done with the segment tree(not sure it will pass the time limit) or you can use the special queue which allows to add and remove elements and to take a maximum. Last one will work in O(n * log(ANS * eps))

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks. After thinking about using binary search its not hard. Checking can be done with multiset in O(nlog n).

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

Binary search in the answer isn't needed. Consider taking partial sums si = a1 + ... + ai, with s0 = 0. Then the average of segment (i, j] is equal to . Look now for every index i the point pi = (i, si). Now the average of a segment [i, j) is the slope of points pi and pj, if we fix the right point j, we need to look for the point pi with A ≤ j - i ≤ B that maximize the slope with pj. Isn't difficult to prove that this point will be in the lower hull of the candidates points. Plus if we look the slopes with the points in the lower hull, the slope first increase and then decrease so we can do a binary search for find the optimal point. This give us an solution, without doing binary search on doubles!!!. And I think (I'm not quite sure now) that it can be improved to an O(n) since we only need the global optimum.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you find a lower hull on interval [i-B, i-A]? you should insert and delete points in CH

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

      The point are added in increasing x coordinate, so we can update the lower hull in O(1) amortized, using a variant of Andres's Scan (page.mi.fu-berlin.de/panos/cg13/l02.pdf). When we move the "windows" we need to delete the leftmost point in the lower hull, we can do it if the hull is stored in a deque. If you need more details, I can be more precise.

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

        It's okay if you can explain what happens in this case :

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ah, I get now what yo meant before. There can be points that can be included in the convex hull when we delete the first point. If there isn't a upper bound in the length of subarray my approach should work. But we can overcome with an extra factor, for an solutions, not so nice tough. The idea is add a point to the convex hull where it can be candidate, we can do it building a segment tree where each node is an lower hull, for query a point we only have to calculate the optimums point in O(logn) hulls. Sorry, it was my mistake.

          → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give a link to the problem?

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Here's an O(n)-time algorithm for the problem:

https://arxiv.org/abs/cs/0311020

→ Reply