ram396's blog

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

Comments Comments (5)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can elements of A be negative?

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

    No

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
      ← 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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
        ← 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
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
          ← 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