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

Автор Death_Scythe, история, 7 лет назад, По-английски

Hi! I have been trying the following problem for some time now and haven't been able to come up with a solution better than O(N^2).

Given an array A with N integers, define maxi, j to be the maximum value in A[i..j] and mini, j to be the minimum value in A[i..j]. A[i..j] denotes the subarray starting from index i and ending at j. Compute the following sum:

Please let me know if this problem is available on some OJ.

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    I guess the editorial solution should work with my problem. I have to sum Vi without the pi - 1 factor.

    Thanks for the help!

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      there is 1 more solution with divide and conquer, for a range [l, r], fix mid = (l + r) / 2 and find sum of max(i,j) * min(i, j) for ranges (i, j) that contain mid in O(r — l + 1)

      then u remove mid and solve for (l, mid — 1) and (mid + 1, r)

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

        I did consider this way of thinking but I do not see how to compute the answer for ranges containing mid in linear time.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          range [i, j] containing mid will be a suffix [i, mid] and prefix [mid + 1, j]

          now you have to precalculate all suffix maxima , minima and same for prefix

          And you have 4 cases: minimum is in suffix, but maximum is in prefix

          or vice versa

          Or Both are in prefix, or Both are in suffix

          you need to treat all 4 cases separately

          note that suffix maxima is increasing, suffix minima is decreasing, prefix maxima is increasing, prefix minima is decreasing

          Now think how you can solve this with 2 pointers approach

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

I think that it can be solved using divide and conguer. The complexity will be O(nlogn)

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Another very similar problem is Norma from COCI 2014/15.

You can submit it here.