Skeef79's blog

By Skeef79, history, 3 years ago, translation, In English

Recently I've come up with this problem:

You are given an array $$$a_1, a_2, \dots, a_n$$$ of positive integers.

You need to find $$$l$$$, $$$r$$$ such that $$$\frac{\prod_{i=l}^{r} a_i}{r-l+1}$$$ is maximum over all possible $$$l,r$$$ $$$(l \leq r)$$$.

Is it possible to solve this faster than $$$O(n^2)$$$? This problem looks like something well-known, but I am not sure.

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Skeef79 (previous revision, new revision, compare).

»
3 years ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

Let yi = sum of ai up to index i, xi = i. Then for some (l, r) the value of the abovementioned formula is (yr — yl) / (xr — xl) , So i think you can go from left to right and maintain a lower hull of the (xi, yi)'s or something along those lines.

Edit : I wrote the answer for the sum, because you have used sum in the above formula, do you mean product or sum ?

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

    Whoops, i mean product... Sorry, my bad

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 5   Vote: I like it +19 Vote: I do not like it

      No worries. Okay i am going to forget about the product of numbers being possibly to large to fit into any data type in the following section. Let yi = product of ai up to index i. Product on range = yr/yl * 1/(r — l) reverse the formula and instead minimize : (yl*r — yl*l)/(yr) . Now look at; yr as a constant, yl as your "k", and -yl*l as your "b", and at "r" as your "x", so you have a line of form ( k*x + b ) / constant . So you can solve it again with lines, maintaining upper/lower envelope as you iterate from left to right.

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

        Nice solution if numbers are small.

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

Bin search on answer

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Skeef79 (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +172 Vote: I do not like it

Denote $$$P = \prod_{i=1}^N a_i$$$. One obvious answer is $$$\frac{P}{N}$$$. Now, this answer might not be optimal, and one may give up on some values $$$a_i$$$ for the sake of a lower numerator.

However, note that the product of the numbers that you give up must never exceed $$$N$$$. Also, note that it's never optimal to have $$$a_l = 1$$$ or $$$a_r = 1$$$. These two observations imply that there are at most $$$\log^2 N$$$ "interesting" pairs $$$(l, r)$$$.

For each such pair you have to compare $$$\frac{1}{r-l+1} \prod_{i=l}^r a_i$$$. However, these numbers might be really big. Instead, note that that product above equals, in fact, $$$\frac{P}{(r-l+1)p}$$$, where $$$p$$$ is the product of the numbers that you're not including in your range (and should be smaller than $$$N$$$), and $$$P$$$ is the product of all numbers.

Then, you can just compare $$$(r-l+1)p$$$ instead of those huge numbers.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Why cannot we work on logarithm of numbers, and convert it to classic maximum average of subarray task.
    https://codeforces.me/blog/entry/21103
    Correct me if I am wrong,let's say $$$f(l,r) = \sum_{i=l}^r log(a_i)$$$ and $$$g(l,r) = \prod_{i=l}^r a_i $$$
    So , maximize $$$g(l,r) / (r-l+1) $$$ is equivalent to maximize $$$f(l,r) / (r-l+1)$$$ as $$$r-l+1$$$ is just dividing factor.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    The problem should ask for the subarray's endpoints which maximize the value.

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

    Thank you! Awesome solution.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Skeef79 (previous revision, new revision, compare).

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

UPD: Wrong solution