dcordb's blog

Can this DP be solved in less than O(N * K)
By dcordb, history, 6 years ago, In English

Given an array with N elements you need to choose exactly K non-consecutive elements from it such that the sum of the elements will be minimum.

Constraints:

  • 1 ≤ N ≤ 105
  • 1 ≤ K ≤ N
  •  - 109 ≤ ai ≤ 109

I know how to solve this in O(N·K) by using DP(i, m) =  minimum sum that can be obtained in prefix i taking exactly m elements.

Can it be done faster than that? Thanks beforehand.

EDIT: I had an idea that was do a binary search on the answer, let's say answer should be less or equal than x, then for a prefix i the values that m can take so that DP(i, m) ≤ x are consecutive so I transformed the DP to DP(i) =  range of the valid m values. But the problem with this is how to merge DP(i - 1) with DP(i - 2) in time.

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

Comments Comments (7)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it +20 Vote: I do not like it

(I) For every 1 ≤ i ≤ n, insert i with cost ai into a priority_queue whose top element has the minimum cost. And keep a linked-list 1, 2, 3, ..., n.

(II) Repeat the following steps k times:

(II.a) Pick the top element x from the priority_queue.

(II.b) Add the cost of x into the answer.

(II.c) Change the cost of x into costprex + costnxtx - costx, where prex and nxtx are the previous and next element of x in the linked-list.

(II.d) Delete prex and nxtx from the linked-list and the priority_queue.

(II.e) Insert x with new cost into the priority_queue.

This works in .

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

    Thank you. Let me see if I understood you correctly, changing ax into aprex + anxtx - ax every time that ax is on top of the queue what it does is:

    1. take ax
    2. take ax - 1, ax + 1
    3. take ax - 2, ax, ax + 2
    4. take ax - 3, ax - 1, ax + 1, ax + 3
    5. take ax - 4, ax - 2, ax + 2, ax + 4

    and so on right? but everytime you do this you delete prex and nxtx, why is this optimum? Can't it be that later on you can get better solution by taking other x and possibly some prex and nxtx already erased?

    It's not clear to me why this is right, could you explain more?

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

      If x is not the minimum after changing cost, you will pick another x.

      And the correctness can be proved by minimum cost flow.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        I understand the overall approach, but I'm don't know how to handle border cases.

        For Example:

        If we select a1 (The sequence is 1-based) Then we will push a0 + a2 — a1 into the priority queue. The main idea of the approach is that if we select this element of the priority_queue, it is supposed to "unselect" the original one and select the two adjacent ones such that the k becomes k + 1. However, in the example, if I select the element "a0+a2-a1", the number is selected element remained unchanged because a0 does not exist. however, in the loop k increments by 1.

        How am I supposed to fix this problem.

        Sorry for Bad English

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

          If you select a1, it means a1 ≤ a2, so you will never choose a2 because a1 is better in both position and cost.

          So in such case, you can just ignore the final step.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            Tks a lot, your suggestion really helps me implementing the algorithm. At last, I wish you advance to legendary grandmaster soon.

            → Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Alternative solution : You can solve it using the so-called "Aliens trick", which is mentioned here. The proof of "convexity" can be done with minimum-cost-flow.

→ Reply