Блог пользователя Hoyda

Problem: Maximal Average on Array
Автор Hoyda, история, 7 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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.

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you give a link to the problem?

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

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

→ Ответить