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

Автор Skeef79, история, 3 года назад, перевод, По-английски

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.

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

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

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

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

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 5   Проголосовать: нравится +19 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Bin search on answer

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

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

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

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

UPD: Wrong solution