1D/1D Dynamic Programming Optimization - Part I

Post date: May 4, 2013 3:17:03 AM

This series of blog posts will be a rough translation of this document.

(For more DP optimization tricks see http://codeforces.com/blog/entry/8219)

What we mean by 1D/1D DP is that there are states, each depending on states. The time complexity to solve these directly is thus , but a large number of these can be solved faster. Here we will discuss a few basic classical ideas for optimizing this.

Functions in these posts will be denoted in two ways. means that the values of the function can all be precomputed (e.g. constants given in the inputs), while means that the value must be computed within the dp itself. However, once it has been computed it can be cached for future lookups.

Model 1:

This model should be familiar to everyone. However, when certain conditions are met, there is an associated monotonicity property that allows it to be solved in time.

The required condition is the quadrangle inequality: .

Let . Given that the above condition is satisfied, then we have that .

From a practical point of view, we don't need to prove that w satisfies such an inequality, it's easiest to just list out a few values of w and check.

The simplest way to take advantage of this monotonicity is that when deciding dp(x), to start from k(x-1) instead of from 1. However, this only reduces the constant and doesn't improve the asymptotic runtime.

So far we've been thinking along the lines of "for each x, what is the value of k(x)?" But now, let's try to approach this through "for each i, which values of x could possibly have k(x) = i?"

At the start, i=1 and we have no information, so every x could have k(x) = 1.

k(x) = 111111111111111111111111111111111111111111111111111111111111111

At this point, we can decide the value of dp(2), since the only possible value for k(2) is 1. Once we have the value of dp(2), we can go through every value of x and update the current estimate of k(x) with whether i=2 is better than i=1. But, notice that from the monotonicity of k that the result must be of this form:

k(x) = 111111111111111111111111111111222222222222222222222222222222

What this means is that we can use binary search to find the turning point: for a certain i, if i=2 is better, then for everything above x, i=2 is better; if i=1 is better, then for everything below x, i=1 is better.

After updating 1 and 2 we can now determine dp(3) by just looking at the 3rd position and seeing what value k(3) is. Using dp(3) we can update our estimates of k(i), and once again by monotonicity the only possible forms that are possible are these two:

k(x) = 11111111111111111111111111111111122222222222222222233333333333

k(x) = 11111111111111111111111111333333333333333333333333333333333333

Thus, our approach to updating with dp(3) is then:

• Check the first value of x where k(x)=2 to see if i=3 is better.
  • If it is, binary search in the k(x)=1 region to find the turning point, and mark everything behind it with k(x)=3
  • If it isn't, binary search in the k(x)=2 region instead

The overall algorithm should now be clear. We should store the beginning of each segment in a vector. Whenever we consider a new value of i, perform the following to update the segments:

1. While the new value of i is better than the value at the back of the vector, pop the back.
2. Binary search in the current segment to find the turning point, and push this value of i together with the turning point onto the back of the vector.

Since each value of i will only be pushed&popped from the vector at most once, the cost of updating the structure is

. However, because of the binary search, the overall runtime is

.

Let's look at some example questions:

Example 1: Batch Scheduling

It is not hard to come up with a simple dp solution, letting dp(x) be the minimum total cost of processing jobs 1..x and considering processing jobs i..x in the same batch, we have:

To calculate the number of batches up to x, we can store that in another array. Unfortunately, this is a dp and will time out.

However, this isn't quite in the format of model 1 above, so we can't apply the speed up directly. However, noticing that starting a new batch effectively pushes the start time of everything after it by S - and that we know how much delaying things by S costs, we might as well incorporate that into the cost of the current batch, leading to this dp:

which fits the form

In this case it is also not hard to prove that the quadrangle inequality holds.

Applying the above method we reduce the complexity to and the solution (http://pastebin.com/kEBEyMxd) passes.

Example 2: Land Acquisition

If we sort the land by height, then you can convince yourself that the optimum can be achieved by buying consecutive pieces of land. Thus a simple dp is

However, this fails the quadrangle inequality. Let us try to make a simplification.

If we graph the plots of land (length vs width):

It's not hard to see that the red dots can be ignored, since there exists a piece of land that dominates it in both length and width, and thus it can come for free with that piece. These points can be removed in a single line sweep. Then, the remaining points are now automatically ordered in non-increasing width so the above equation becomes:

Once again this can be proved to satisfy the quadrangle inequality, and you can apply model 1 to solve the problem in .

These two examples were all direct applications of the monotonicity of k, which in the end only leads to an solution. However, both of these problems can actually be solved in

using another model that will be introduced in Part 3 of the series.