ram396's blog

Got this question in OA yesterday,can anyone solve this
By ram396, history, 5 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

»
5 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
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can elements of A be negative?

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

    No

    → Reply
    • »
      »
      »
      5 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
      • »
        »
        »
        »
        5 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
        • »
          »
          »
          »
          »
          5 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
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can u provide the code?

          → Reply