### ram396's blog

By ram396, history, 6 weeks ago,

Given an array of size n.You need to select those two different indices such that quirk between them is maximum.Quirk Q(i,j)=

• -21

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by ram396 (previous revision, new revision, compare).
 » 6 weeks ago, # |   0 Can elements of A be negative?
•  » » 6 weeks ago, # ^ |   0 No
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +2 Well if elements aren't negative then j should always be equal to n. And i you can traverse in linear time to find the maximum.Edit: only if c is +ve, otherwise j can be other things.
•  » » » » 6 weeks ago, # ^ | ← Rev. 3 →   +13 If $A[i]$ or $c$ is allowed to be negative:Note that: \begin{align*} Q(i, j) &= \left(\sum(A[k] + c(j - i))\right) + 2ij \\ &= \sum(A[k]) + c(j - i)(j - i + 1) + 2ij \\ &= ps[j] - ps[i - 1] + c(j^2 - ij + j - ij + i^2 - i) + 2ij \\ &= ps[j] - ps[i - 1] + cj^2 - 2cij + cj + ci^2 - ci + 2ij \\ &= (ps[j] + cj^2 + cj) + (ci^2 - ci - ps[i - 1]) + ((2 - 2c)ij) \\ \end{align*}We define the following functions: $F(x) = ps[x] + cx^2 + cx$ $C(x) = cx^2 - cx - ps[x - 1]$ $M(x) = (2 - 2c)x$. For each $j$, you need to find $i$ such that $F(j) + M(i)j + C(i)$ is maximized. You can use convex hull trick to do so in $O(N \lg N)$ time.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 That is a wonderful new thing which probably won't be useful for me to learn at this stage, but can you take a quick look at the latest question I asked in my blogs here? I think this problem can be solved using what you call a "convex hull trick" ? Am I right?. In brief I want the maximum of $a_1(K - i) - b_1, a_2(K - i) - b_2, \ldots, a_n(K - i) - b_n$ after each time I change i from 0 to K — 1.
•  » » » » » 5 weeks ago, # ^ |   0 can u provide the code?