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

Got this question in OA yesterday,can anyone solve this
Автор ram396, история, 5 месяцев назад, По-английски

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
  • Проголосовать: не нравится

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

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

→ Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can elements of A be negative?

→ Ответить
  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No

    → Ответить
    • »
      »
      »
      5 месяцев назад, # ^ |
      ← 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.

      → Ответить
      • »
        »
        »
        »
        5 месяцев назад, # ^ |
        ← 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.

        → Ответить
        • »
          »
          »
          »
          »
          5 месяцев назад, # ^ |
          ← 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.

          → Ответить
        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          can u provide the code?

          → Ответить