suzie_q's blog

By suzie_q, history, 3 years ago, In English

We are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Consider the following recurrence relation:

$$$f(i) = \displaystyle \min_{b[i]\; \leq\; j\; <\; i}\big\{f(j)+ \max(a[j+1], \dots, a[i])\big\}$$$

We are interested in calculating $$$f(n)$$$. Is there a way to calculate it with the time complexity being better than $$$\mathcal{O}(n^2)$$$?

UPD: I forgot to mention that the array $$$b$$$ is increasing (i.e. $$$b[i] \leq b[i+1]$$$). Don't know if that helps though...

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
3 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

If I understood the task conditions correctly, you can use a segment tree and a maxque. Calculate in process a and replace in the tree of segments the number that will be added to f(i). Of all of them, find the minimum and count further

The final asymptotics of O(n log n)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I'm not sure I understand your approach. Could you elaborate, please?

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

      going from left to right through the array, we will count f(i) for each i. Next, we will use a stack with a maximum. In short, it will store the positions of all local maxima starting from the beginning (more details in the picture).  I.e. we store the positions in which the maximum will change. next, when we add another number to our stack, the following happens: We remove from the stack all numbers that are smaller than ours. If we do this, it is obvious that now the maximum from the number j to our i is the nearest element to the right or equal to us, which lies in the stack. Now we can imagine that each element from the stack is actually a segment on which this element will be the maximum. Now we just have to make a tree of segments with adding on the segment and searching for the maximum on the segment, simultaneously deleting and changing the segments in the stack and everything is ready.

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

        Are you saying that to calculate $$$f(i)$$$ we should consider only those values of $$$j$$$ that are between the index of the previous element greater than $$$a[i]$$$ and $$$i-1$$$?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +21 Vote: I do not like it

          let met explain it a little bit better.
          we find the values of $$$f$$$ from left to right. to do that, we maintain a range add-range min segment tree $$$seg$$$, such that when we are calculating $$$f_i$$$, $$$seg_j$$$ is equal to $$$f_j + max(a_{j+1} , \cdots , a_i)$$$. then, we just make a query for segment $$$[b_i , i)$$$ to find the value of $$$f_i$$$.

          how to update our segment tree?

          hope it helps!

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

            But isn't the complexity $$$O(n^2)$$$ in the worst case?

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +21 Vote: I do not like it

              no, because if we add something to $$$(g_j , j]$$$ for some $$$j$$$, we will never add something else to a segment ending at $$$j$$$, and this results in at most $$$O(n)$$$ additions and total complexity will be $$$O(nlogn)$$$.
              actually, complexity analysis is the same with complexity analysis of finding values of $$$g$$$, each "set $$$seg_i$$$ to $$$f_i$$$" corresponds to a push operation on stack and each "jump from $$$j$$$ to $$$g_j$$$" corresponds to a pop operation on stack.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Is b strictly increasing or non-decreasing? I think the former condition makes the problem a lot easier.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1d1d?

i think that we can use it here

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Isn't the fact that we want the minimum over all $$$j$$$ such that $$$b[i] \leq j < i$$$ going to ruin this approach?

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

      I think that will help us. Because for 1D1D (i might be wrong) we need to $$$opt[i] <= opt[i + 1]$$$ everytime, so that only helps us, because $$$b[i] <= b[i + 1]$$$