ram396's blog

Got this question in OA yesterday,can anyone solve this
By ram396, history, 10 months ago, In English

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

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can elements of A be negative?

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

    No

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
        ← Rev. 3   Vote: I like it +13 Vote: I do not like it

        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.

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

          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.

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

          can u provide the code?

          → Reply