Quadrangle Inequality Optimization
Quadrangle inequality optimization exploits decision monotonicity in a DP recurrence. It is also commonly known as DP optimization by decision monotonicity.
Basics
Consider the simplest case. We want to solve the following family of optimization problems:
We assume here that the cost function \(w(j,i)\) can be computed in \(O(1)\) time.
Conventions
A dynamic programming recurrence can often be written as a family of optimization problems. Take equation (1): the problems are parameterized by \(i\), and both the objective function and the feasible region may depend on \(i\). Each problem asks, for a given \(i\), for a feasible solution \(j\) that minimizes the objective function. For convenience, we call the optimization problem with parameter \(i\) "problem \(i\)", a feasible solution \(j\) of it "decision \(j\)", and the value of the objective function at an optimal solution "state \(f(i)\)". We also write \(\operatorname{opt}(i)\) for the smallest optimal decision point of problem \(i\).
In general, solving all these problems takes \(O(n^2)\) time, because for problem \(i\) we have to consider every possible decision \(j\). When decision monotonicity holds, the decision space shrinks considerably and the total complexity improves.
- Decision monotonicity: \(\operatorname{opt}(i_1) \leq \operatorname{opt}(i_2)\) for all \(i_1 < i_2\).
Remark
The set of optimal decisions of problem \(i\) need not be an interval. Decision monotonicity can in fact be defined on these sets. For sets \(A\) and \(B\), define \(A \leq B\) if and only if \(\min\{a,b\}\in A\) and \(\max\{a,b\}\in B\) for all \(a\in A\) and \(b\in B\). This implies that the smallest (largest) optimal decision point is monotone, which is the definition adopted here. Everything this article states about the smallest optimal decision point also holds for the largest one. However, the smallest optimal decision of a larger problem can be strictly smaller than the largest optimal decision of a smaller problem; that is, \(\mathop{\mathrm{optmax}}(i_1) > \mathop{\mathrm{optmin}}(i_2)\) may hold for some \(i_1 < i_2\). So make sure your code always finds the smallest optimal decision point, or always the largest.
On the other hand, the problems that share the same smallest optimal decision form an interval. As a function of the smallest optimal decision, this interval is strictly increasing: given \(j_1 = \operatorname{opt}(i_1)\) and \(j_2 = \operatorname{opt}(i_2)\), if \(j_1 < j_2\) then \(i_1 < i_2\). In other words, if \([l_{j_1},r_{j_1}]\) and \([l_{j_2},r_{j_2}]\) are the intervals of problems for which the decisions \(j_1 < j_2\), respectively, are the smallest optimal decision, then \(r_{j_1} < l_{j_2}\).
The most common way to establish decision monotonicity is the quadrangle inequality. Depending on the context, this property is also called the Monge property (of a matrix \(A_{j,i}\)) or submodularity (of a function \(f([j,i])\) whose argument is an interval).
-
Quadrangle inequality: if for all \(a\leq b\leq c\leq d\) we have
\[ w(a,c)+w(b,d) \leq w(a,d)+w(b,c), \]then the function \(w\) is said to satisfy the quadrangle inequality (in short, "crossing costs no more than nesting"). If equality always holds, \(w\) is said to satisfy the quadrangle identity.
Unless stated otherwise, we assume \(a\leq b\leq c\leq d\) from here on. The quadrangle inequality is a sufficient but not necessary condition for decision monotonicity.
Theorem 1
If \(w\) satisfies the quadrangle inequality, then problem (1) has decision monotonicity.
Proof
We give a proof by contradiction. Suppose that \(a = \operatorname{opt}(d) < \operatorname{opt}(c) = b\) for some \(c < d\). Then \(a < b \leq c < d\). By optimality, \(w(a,d) \leq w(b,d)\) and \(w(b,c) < w(a,c)\), so \(w(a,d) - w(b,d) \leq 0 < w(a,c) - w(b,c)\), which contradicts the quadrangle inequality.
The quadrangle inequality can be read as saying that, on a suitable domain, the mixed second difference \(\Delta_i\Delta_jw(j,i)\) of \(w\) is non-positive.
Several common algorithms use decision monotonicity to bring the complexity down to \(O(n\log n)\). They differ in scope, in how hard they are to implement and in speed, so choose the one that fits the situation; this depends mainly on the properties of \(w(j,i)\). Unless stated otherwise, this article assumes random access to \(w(j,i)\): any value can be looked up or computed in \(O(1)\) time. But \(w(j,i)\) is not this easy to compute in every problem. So besides the basic case, this article also shows how to optimize a DP by decision monotonicity when \(w(j,i)\) only has one of the following properties:
- Incremental access: \(w(j,i)\) can be obtained from \(w(j\pm 1,i)\) or \(w(j,i\pm 1)\) in \(O(1)\) time (as in Mo's algorithm).
- Dynamic evaluation: computing \(w(j,i)\) depends on \(\{f(j'):j' < j\}\), so \(f\) and \(w\) can only be computed in order. The interval partition problem with an unrestricted number of intervals, discussed below, is of this kind.
The two properties are not mutually exclusive: \(w(j,i)\) may require dynamic evaluation and support only incremental access at the same time.
Divide and conquer
To compute all states it is enough to find all optimal decision points. To find \(\operatorname{opt}(i)\) for all \(1 \leq i \leq n\), first compute \(\operatorname{opt}(n/2)\), then compute \(\operatorname{opt}(i)\) separately for \(1 \leq i < n/2\) and for \(n/2 < i \leq n\). At this point we know that \(\operatorname{opt}(i)\) lies between \(1\) and \(\operatorname{opt}(n/2)\) (inclusive) in the first half, and between \(\operatorname{opt}(n/2)\) and \(n\) (inclusive) in the second half. Handle the two subintervals in the same way, until the optimal decision of every problem is known. Keeping track of the lower and upper bounds of the search during the recursion keeps the complexity at \(O(n\log n)\): the recursion tree has \(O(\log n)\) levels, and on each level a single decision point is evaluated at most twice, so the total number of evaluations is \(O(n\log n)\).
Reference implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | |
Besides the basic random-access case, the divide and conquer algorithm also works when \(w(j,i)\) supports only incremental access. Maintain a cursor \((j,i)\) together with the value \(w(j,i)\); whenever a new value is needed, move the cursor step by step to the new position, updating the value along the way. This still takes \(O(n\log n)\) time; the section Simplified LARSCH algorithm below discusses this in more detail. The divide and conquer algorithm cannot, however, handle the case where \(w(j,i)\) requires dynamic evaluation, because it has no way to compute the smallest optimal decision \(\operatorname{opt}(n/2)\) at the midpoint before the problems in the left half are solved.
Binary-search queue
For each decision point \(j\), the problems \(i\) for which it is the smallest optimal decision point form an interval. A monotonic queue can record, for each decision point so far, the interval of problems it solves; the optimal solution of a problem is then computed from the decision points stored in the queue.
Concretely, the algorithm goes through the decision points in order. When it reaches decision point \(k\), the queue holds a triple for each viable decision point \(j\) so far: \(j\) itself and the left and right endpoints \(l_j\) and \(r_j\) of the interval of problems it solves. For the problems in \([l_j,r_j]\), \(j\) must be the smallest optimal decision among the decision points considered so far (those in \([1,k]\)). At any moment, the decisions stored in the queue need not be consecutive, but the unsolved problems \([k,n]\) must be the disjoint union of the problem intervals stored in the queue.
To show that, while the queue is being updated, the problems \(i\) for which decision point \(j\) is the smallest optimal decision always form a contiguous interval, we need a slightly stronger version of the earlier result:
Corollary 1
Let \(\operatorname{opt}_k(i)\) be the smallest optimal decision of problem \(i\) when only the decisions in \([1,k]\) are considered. If \(w\) satisfies the quadrangle inequality, then \(\operatorname{opt}_k(i_1) \leq \operatorname{opt}_k(i_2)\) for all \(i_1 < i_2\).
Proof
Let \(M\) be a sufficiently large positive real number. The function \(w'(j,i) = w(j,i) + M[j > k]\), where \([\cdot]\) is the Iverson bracket, still satisfies the quadrangle inequality. Consider the auxiliary DP with cost function \(w'\). In it, no decision \(j > k\) can be the smallest optimal decision of any problem \(i\), that is, \(\operatorname{opt}'(i) = \operatorname{opt}'_k(i) = \operatorname{opt}_k(i)\). Applying Theorem 1 to the auxiliary DP gives the corollary.
The algorithm proceeds as follows:1
- Initially the queue is empty. As with a monotonic queue, every time the next decision \(j\) is considered there is a dequeue step and an enqueue step.
- Dequeue: first remove the previous problem \(j-1\) from the queue. If the interval of problems solved by the decision at the front ends exactly at \(j-1\), pop the front; otherwise set the left endpoint of that interval to \(j\).
- Enqueue: to enqueue decision \(j\), first compare it with the decision \(j'\) at the back.
- If the new decision \(j\) is strictly better than the existing decision \(j'\) for problem \(l_{j'}\), that is, if \(w(j,l_{j'}) < w(j',l_{j'})\), pop \(j'\) from the back. Repeat until the queue is empty or the decision \(j'\) at the back is better than \(j\) for problem \(l_{j'}\).
- If the queue is now empty, enqueue \((j,j,n)\): decision \(j\) is taken to be optimal for all unsolved problems.
- If the decision \(j'\) at the back is also no worse than \(j\) for problem \(r_{j'}\), then when \(r_{j'} < n\), enqueue \((j,r_{j'}+1,n)\) to record that \(j\) is the smallest optimal decision for the problems \([r_{j'}+1,n]\); otherwise \(j\) need not be enqueued, since it is no better than the existing decisions.
- In the remaining case, the decision \(j'\) at the back is strictly better than \(j\) for problem \(l_{j'}\) and strictly worse for problem \(r_{j'}\). So there is a problem \(i\in(l_{j'},r_{j'}]\) such that \(j'\) is the smallest optimal decision for the problems \([l_{j'},i-1]\) and \(j\) is the smallest optimal decision for the problems \([i,r_{j'}]\). Use binary search to find the smallest \(i\in[l_{j'},r_{j'}]\) with \(w(j,i) < w(j',i)\), update the right endpoint \(r_{j'}\) of the interval at the back to \(i-1\), and enqueue \((j,i,n)\).
- Once decision \(j\) has been processed, all decisions up to \(j\) have been handled. The decision at the front is now the smallest optimal decision of problem \(j\), and we can record the corresponding optimal solution.
Reference implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | |
As in a monotonic queue, each decision point is enqueued at most once and dequeued at most once. Dequeuing takes \(O(1)\) and enqueuing takes \(O(\log n)\) (it may need a binary search), so the total time is \(O(n\log n)\).
Because the binary-search queue algorithm considers all problems and decision points in order, it works when \(w(j,i)\) requires dynamic evaluation. This is its advantage over the divide and conquer algorithm. But its binary search step relies on random access to \(w(j,i)\), so it does not work when \(w(j,i)\) supports only incremental access.
Example 1: [POI2011] Lightning Conductor
Given a sequence \(a_1,a_2,\cdots,a_n\) of length \(n\), find for each \(1 \leq i \leq n\) the smallest non-negative integer \(f_i\) such that
Approach
Rearranging the inequality gives \(f_i = \max_{j}\{a_j+\sqrt{|i-j|}-a_i\}\) for the integer we want. Consider the case \(j \leq i\) first (the other case is similar). We get the recurrence
Since \(-\sqrt{x}\) is convex, the function \(w(j,i) = -a_j-\sqrt{i-j}+a_i\) satisfies the quadrangle inequality (the details are given later), so the algorithms above solve this problem in \(O(n\log n)\) time.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | |
Simplified LARSCH algorithm
Neither of the two algorithms above can handle the case where \(w(j,i)\) both requires dynamic evaluation and supports only incremental access. This section presents an algorithm that overcomes both difficulties at once. It is a simplified version of the LARSCH algorithm2 that Larmore and Schieber proposed in 1991, hence the name simplified LARSCH algorithm. The original algorithm solves DP problems with decision monotonicity in \(O(n)\) time, but it is harder to implement and is not covered here.
We again use divide and conquer. When solving the problems in the interval \((l,r]\), assume that the following is known:
- the smallest optimal decision \(\operatorname{opt}(i)\) and the optimal value of every problem \(i\) in \([1,l]\), and
- the smallest optimal decision \(\operatorname{opt}_l(r)\) and the optimal value of problem \(r\) when only the decisions in \([1,l]\) are considered.
When the problems in \((l,r]\) have been solved, their smallest optimal decisions and optimal values must be known.
Let \(\textit{mid}\) be the midpoint of \((l,r]\). The procedure is as follows:
- Go through the decisions \(j\in[\operatorname{opt}(l),\operatorname{opt}_l(r)]\) and update the smallest optimal decision and the optimal value of problem \(\textit{mid}\).
- Recursively solve the problems in \((l,\textit{mid}]\).
- Go through the decisions \(j\in(l,\textit{mid}]\) and update the smallest optimal decision and the optimal value of problem \(r\).
- Recursively solve the problems in \((\textit{mid},r]\).
Before starting the recursion on the whole interval \([1,n]\), update the problems \(i\in\{1,n\}\) with decision \(j=1\). The recursion stops when it reaches \(l=r\).
Reference implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | |
We first show that the algorithm is correct. It suffices to check that the preconditions above hold before each recursive step (steps 2 and 4). By Corollary 1 from the previous section, \(\operatorname{opt}(l)=\operatorname{opt}_l(l)\le\operatorname{opt}_l(\textit{mid})\le\operatorname{opt}_l(r)\), so \(\operatorname{opt}_l(\textit{mid})\) is known after step 1, and the preconditions for solving \((l,\textit{mid}]\) recursively hold before step 2. Since \(\{\operatorname{opt}(i):i\in[1,l]\}\) was already known and step 2 produces \(\{\operatorname{opt}(i):i\in(l,\textit{mid}]\}\), all of \(\{\operatorname{opt}(i):i\in[1,\textit{mid}]\}\) is known afterwards. And since \(\operatorname{opt}_l(r)\) was known, \(\operatorname{opt}_\textit{mid}(r)\) is known after step 3. So the preconditions for solving \((\textit{mid},r]\) recursively also hold before step 4.
Next we show that the algorithm still runs in \(O(n\log n)\). The recursion tree has \(O(\log n)\) levels. Each node on a level goes through the decisions in \([\operatorname{opt}(l),\operatorname{opt}_l(r)]\) and those in \((l,\textit{mid}]\). Because \(\operatorname{opt}(l)\le\operatorname{opt}_l(r)\le\operatorname{opt}(r)\), each decision point is visited only \(O(1)\) times per level, so the number of visits on each level of the recursion tree is \(O(n)\) in total. If one access to or evaluation of \(w(j,i)\) costs \(O(1)\), the algorithm takes \(O(n\log n)\) time.
The algorithm still runs in \(O(n\log n)\) in some cases where \(w(j,i)\) supports only incremental access. Maintain a separate cursor \((j,i)\), with the current value of \(w(j,i)\), for step 1 and for step 3. Whenever a new value is needed, move the cursor \((j,i)\) step by step from where it was last used to the new position, updating \(w(j,i)\) along the way. It is easy to check that over the whole traversal of the recursion tree these brute-force moves number \(O(n\log n)\) in total, so the algorithm still takes \(O(n\log n)\) time.
Proof of complexity without random access
We only need to show that the cursors move \(O(n\log n)\) times in total. Let \(A\) and \(B\) be the cursors of steps 1 and 3. We can in fact guarantee the following: before the problems in \((l,r]\) are solved, cursor \(A\) is at \((\operatorname{opt}(l),l)\) and cursor \(B\) is at \((l,l)\); afterwards, cursor \(A\) is at \((\operatorname{opt}(r),r)\) and cursor \(B\) is at \((r,r)\).
We construct the following rule for moving the cursors. In step 1, moving cursor \(A\) along the path
leaves cursors \(A\) and \(B\) both at the positions required before solving the problems in \((l,\textit{mid}]\). In step 2, by the guarantee, cursor \(A\) moves to \((\operatorname{opt}(\textit{mid}),\textit{mid})\) and cursor \(B\) moves to \((\textit{mid},\textit{mid})\). In step 3, moving cursor \(B\) along the path
leaves cursors \(A\) and \(B\) both at the positions required before solving the problems in \((\textit{mid},r]\). In step 4, by the guarantee, cursor \(A\) moves to \((\operatorname{opt}(r),r)\) and cursor \(B\) moves to \((r,r)\). Both cursors are now at the positions required after solving the problems in \((l,r]\), so the rule respects the guarantee. It also suffices for all the computations of steps 1 and 3. Counting the moves directly, step 1 needs
moves and step 3 needs
moves. Sum these counts over all nodes of the recursion tree. Within one level, the intervals \([l,r]\) overlap at most at their endpoints, and so do the intervals \([\operatorname{opt}(l),\operatorname{opt}_l(r)]\); hence the total number of moves is \(O(n\log n)\).
This rule sends the cursors through more waypoints than the actual computation does, so the number of times the cursors actually move cannot exceed the estimate under the rule. It is therefore also \(O(n\log n)\).
Since the optimal values \(f(i)\) for \([1,l]\) are already computed before the algorithm solves the problems in \((l,r]\), it also works when \(w(j,i)\) requires dynamic evaluation.
Interval partition problem
Consider the problem of splitting an interval into subintervals. Formally, split the given interval \([1,n]\) into \([a_1,b_1],\cdots,[a_k,b_k]\), where \(a_1=1\), \(b_k=n\), and \(b_{i}+1=a_{i+1}\) for all \(i < k\). A split costs \(\sum_{i=1}^kw(a_i,b_i)\), and the task is to minimize this cost. This gives the following 1D/1D recurrence.
Here \(f(0)=0\). Whenever \(w(j,i)\) satisfies the quadrangle inequality, so does \(f(j-1)+w(j,i)\): the first term has no cross term in \(j\) and \(i\), so it cancels in the mixed difference. But the cost function depends on earlier subproblems, so the transitions can only be computed in order. The first algorithm described above, divide and conquer, therefore does not apply; usually only the binary-search queue algorithm or the simplified LARSCH algorithm is suitable. The complexity is \(O(n\log n)\).
Restricting the number of intervals
The problem above can be made harder by restricting the number of intervals: the interval must be split into \(m\) subintervals. The number of intervals then has to become a dimension of the DP state, and we get the following 2D/1D recurrence.
Here \(f(0,0)=0\), and \(f(0,i)=f(k,0)=\infty\) for all \(1\leq k\leq m\) and \(1\leq i\leq n\). For the same reason as before, \(f(k-1,j-1)+w(j,i)\) satisfies the quadrangle inequality. Computing layer \(k\) no longer depends on results of the same layer, so each layer can be computed with any of the algorithms of the previous section, for a total of \(O(mn\log n)\).
Decision monotonicity in fact allows other optimizations of this problem. The second one relies on the following result. It closely resembles Knuth's optimization, which is described in detail below.
Theorem 2
If \(w\) satisfies the quadrangle inequality, then \(\operatorname{opt}(k-1,i) \leq \operatorname{opt}(k,i) \leq \operatorname{opt}(k,i+1)\) holds for problem (2).
Proof
The second inequality is just decision monotonicity within layer \(k\). The first inequality is the crux.
We prove \(\operatorname{opt}(k,i) \leq \operatorname{opt}(k+1,i)\). Take two partitions of the interval \([1,i]\), numbered in reverse order: \([a_{k},d_{k}],\cdots,[a_1,d_1]\) and \([b_{k+1},c_{k+1}],\cdots,[b_1,c_1]\). In both, the left endpoint of each interval is the smallest optimal decision of the problem at its right endpoint; likewise, considering all possible partitions from right to left, each right endpoint is the smallest optimal decision of the problem at its left endpoint. For example, \(d_j\) and \(c_j\) are the smallest optimal choices for the right endpoint of the leftmost interval when \([a_j,i]\) and \([b_j,i]\), respectively, are split into \(j\) parts. By decision monotonicity, if \(a_{j-1} > b_{j-1}\), that is, \(d_j > c_j\), then \(a_j > b_j\). So if the claim fails, we have \(a_1 > b_1\), and by induction \(a_{k} > b_{k}\). This clearly contradicts the assumption, which proves the claim.
The first inequality can also be proved as follows. Take the same two partitions as in the proof above. If the claim fails, then \(a_1 > b_1\); but since \(a_{k} < b_{k}\), there is a smallest \(j>1\) with \(a_j \leq b_j\). For this \(j\) we have \(a_{j-1} > b_{j-1}\), hence \(d_j>c_j\). We have found a pair of intervals with \(a_j \leq b_j \leq c_j < d_j\). Now recombine the two partitions. The partition \([b_{k+1},c_{k+1}],\cdots,[b_{j+1},c_{j+1}],[b_j,d_j],[a_{j-1},d_{j-1}],\cdots,[a_1,d_1]\) has \((k+1)\) parts, so the optimality assumed above gives
Similarly, the partition \([a_{k},d_{k}],\cdots,[a_{j+1},d_{j+1}],[a_j,c_j],[b_{j-1},c_{j-1}],\cdots,[b_1,c_1]\) has \(k\) parts, so
This inequality is strict, because \(a_1 > b_1\) while, by assumption, \(a_1\) is the smallest optimal left endpoint of the last part among all partitions into \(k\) parts. Adding the two inequalities gives \(w(b_j,c_j) + w(a_j,d_j) < w(b_j,d_j) + w(a_j,c_j)\), which contradicts the quadrangle inequality. This proves the claim.
This result lets us restrict the search range of the decision \(j\). In the implementation, iterate over \(k\) in increasing order and over \(i\) in decreasing order, and search for \(j\) by brute force between the lower and upper bounds already determined; this guarantees a complexity of \(O(n(n+m))\).
Note
The complexity here is not \(O(nm)\). To count correctly, look at the \(n\times m\) matrix of states. For problem \((k,i)\) only the decisions with \(\operatorname{opt}(k-1,i) \leq j \leq \operatorname{opt}(k,i+1)\) are considered, so the problems on one diagonal (those with the same value of \(i-k\)) go through \(O(n)\) decisions in total. There are \((n+m)\) such diagonals, so the total time is \(O(n(n+m))\).
The last optimization comes from the following observation.
Theorem 3
If \(w\) satisfies the quadrangle inequality, then the optimum \(g(k):=f(k,n)\) of problem (2) is a convex function of \(k\).
Proof
We prove \(g(k-1) + g(k+1) \ge 2g(k)\). Take optimal partitions into \((k-1)\) parts and into \((k+1)\) parts, namely \([a_1,d_1],\cdots,[a_{k-1},d_{k-1}]\) and \([b_1,c_1],\cdots,[b_{k+1},c_{k+1}]\). Choose the smallest \(1 \leq j \leq k-1\) with \(c_{j+1} \leq d_j\); it exists because \(c_{k} < n = d_{k-1}\). Since it is the smallest, \(b_{j+1} > a_j\), so \(a_j < b_{j+1} \leq c_{j+1} \leq d_j\). As before, swapping the tails of the two partitions gives the following two interval partitions:
Both have \(k\) parts, so by optimality
The second inequality here is exactly the quadrangle inequality. This proves convexity.
This result guarantees that the problem can be solved with the Aliens trick (WQS binary search). Concretely, take the parameterized cost function \(w_c(j,i):=w(j,i)+c\) and solve the problem without a restriction on the number of intervals; let its optimum be \(f_c(n)\). As the real number \(c\) increases, the number of intervals in the optimal solution decreases monotonically, so a binary search finds the parameter \(c\) for which the optimal number of intervals is exactly \(m\), and the optimum of the original problem is then \(f(m,n) = f_c(n)-cm\). The real number \(c\) can be seen as the Lagrange multiplier of the constraint on the number of intervals. The implementation has many details; see the Aliens trick page. The algorithm runs in \(O(n\log n\log C)\), where \(C\) is the size of the range of the parameter \(c\).
Each of the three algorithms for the interval partition problem with a restricted number of intervals has its strengths and weaknesses under different constraints; choose the one that suits the problem at hand.
Example 3: P4767 [IOI2000] Post Office, Harder Version P6246 [IOI2000] Post Office, Harder Version of the Harder Version
There are some villages along a highway. The highway is represented as an integer axis, and the position of each village is given by a single integer coordinate. No two villages are at the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.
Post offices will be built in some, but not necessarily all, of the villages. Their positions should be chosen so that the sum of the distances between each village and its nearest post office is as small as possible.
Write a program that, given the positions of the villages and the number of post offices, computes the smallest possible sum of the distances between each village and its nearest post office.
Approach
Every village has a nearest post office, so every post office has a set of villages that it serves, and clearly this set is an interval.
So we split the \(n\) villages into \(m\) intervals and then pick one post office in each interval.
It is a standard mathematical fact that the post office for the interval \([i,j]\) should be built at village number \(\left\lfloor\dfrac{i+j}2\right\rfloor\). Prefix sums make \(w(i,j)\) easy to compute.
The problem becomes an interval partition problem with a restricted number of intervals. One can prove that the function \(w\) satisfies the quadrangle inequality, so the optimizations above apply directly.
Implementation 1: the second optimization above, \(O(n(n+m))\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | |
Implementation 2: Aliens trick, \(O(n\log n\log C)\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | |
Interval merging problem
Another class of dynamic programming problems that the quadrangle inequality can optimize is the interval merging problem: \(n\) intervals \([i,i]\) of length one are merged two at a time until the interval \([1,n]\) is obtained. Each merge of \([j,k]\) and \([k+1,i]\) costs \(w(j,i)\), and the task is to find the cheapest way to merge. Such problems have the following 2D/1D recurrence:
Here the initial cost is \(f(i,i)=0\). The brute-force algorithm takes \(O(n^3)\) in total; with decision monotonicity this improves to \(O(n^2)\). The algorithm was first proposed by Knuth for the optimal binary search tree problem and was studied further and generalized by Frances Yao. It is known as Knuth's optimization or the Knuth-Yao speedup.
Besides the quadrangle inequality, decision monotonicity in the interval merging problem also requires the cost function to be monotone under interval inclusion.
-
Monotonicity under interval inclusion: if for all \(a \leq b \leq c \leq d\) we have
\[ w(b,c) \leq w(a,d), \]then the function \(w\) is said to be monotone under interval inclusion.
This is in essence a first-order condition on the cost function: \(w(j,i)\) is decreasing in \(j\) and increasing in \(i\).
Lemma 1
If \(w\) is monotone under interval inclusion and satisfies the quadrangle inequality, then the states \(f(j,i)\) satisfy the quadrangle inequality.
Proof
Let \(a \leq b \leq c \leq d\). We prove \(f(a,d) + f(b,c) \geq f(a,c) + f(b,d)\) by induction on \(d-a\). When \(a=b\) or \(c=d\), the claim is an equality. In the general case, we distinguish cases by the position of \(d'=\operatorname{opt}(a,d)\).
Case 1: \(c \leq d'\) or \(d' < b\), that is, \([b,c]\) is contained in \([a,d']\) or in \([d'+1,d]\).
Assume \(c \leq d'\); the other case is symmetric. Then
Here the first inequality follows from the induction hypothesis \(f(a,c) + f(b,d') \leq f(a,d') + f(b,c)\), the second from monotonicity under interval inclusion, \(w(b,d) \leq w(a,d)\), and the third from the optimality condition \(f(b,d) \leq f(b,d') + f(d'+1,d) + w(b,d)\).
Case 2: \(b \leq d' < c\), that is, \(d'\) lies inside \([b,c]\). Now consider the position of \(c'=\operatorname{opt}(b,c)\).
Assume \(c' \leq d'\), that is, \([b,c']\) is contained in \([a,d']\); the other case is symmetric. Then
Here the first inequality follows from the induction hypothesis \(f(a,c') + f(b,d') \leq f(a,d') + f(b,c')\), the second from the quadrangle inequality \(w(a,c) + w(b,d) \leq w(a,d) + w(b,c)\), and the third from the optimality conditions for \(f(a,c)\) and \(f(b,d)\).
Theorem 4
If \(w\) is monotone under interval inclusion and satisfies the quadrangle inequality, then the smallest optimal decision \(\operatorname{opt}(j,i)\) of problem (3) satisfies
Proof
By Lemma 1, \(f(j,i)\) satisfies the quadrangle inequality. So for fixed \(j\) the objective function \(f(j,k) + f(k+1,i) + w(j,i)\) satisfies the quadrangle inequality as a function of \((k,i)\), and Theorem 1 gives \(\operatorname{opt}(j,i-1) \leq \operatorname{opt}(j,i)\). Note that terms that do not contain both \(k\) and \(i\) do not affect the quadrangle inequality. Similarly, for fixed \(i\) the objective function satisfies the quadrangle inequality as a function of \((j,k)\), so \(\operatorname{opt}(j,i) \leq \operatorname{opt}(j+1,i)\). This completes the proof.
Again, this result restricts the search range of the decision point \(k\). Iterate over the interval length \(i-j+1\) in increasing order, then over all intervals \([j,i]\) of that length; try every \(k\) between \(\operatorname{opt}(j,i-1)\) and \(\operatorname{opt}(j+1,i)\) by brute force to find the optimum \(f(j,i)\), and record the smallest optimal decision \(\operatorname{opt}(j,i)\). Over all intervals of the same length, the decision ranges searched have total length \(O(n)\), and there are \(O(n)\) possible lengths, so the algorithm takes \(O(n^2)\) in total.
Reference implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | |
Classes of functions satisfying the quadrangle inequality
The following properties make it easier to prove that a function satisfies the quadrangle inequality:
Property 1: if the functions \(w_1(j,i)\) and \(w_2(j,i)\) both satisfy the quadrangle inequality (or are both monotone under interval inclusion), then for any \(c_1,c_2\geq 0\) the function \(c_1w_1+c_2w_2\) also satisfies the quadrangle inequality (or is monotone under interval inclusion).
Property 2: if there are functions \(f(x)\) and \(g(x)\) such that \(w(j,i) = f(j)-g(i)\), then the function \(w\) satisfies the quadrangle identity. If \(f\) and \(g\) are decreasing, \(w\) is also monotone under interval inclusion.
Property 3: let \(h(x)\) be an increasing convex function. If the function \(w(j,i)\) satisfies the quadrangle inequality and is monotone under interval inclusion, then the composite function \(h(w(j,i))\) also satisfies the quadrangle inequality and is monotone under interval inclusion.
Property 4: let \(h(x)\) be a convex function. If the function \(w(j,i)\) satisfies the quadrangle identity and is monotone under interval inclusion, then the composite function \(h(w(j,i))\) satisfies the quadrangle inequality.
One clarification first: textbooks in China disagree on the definition of a convex function. Here "convex" means convex downward, that is, a function whose first derivative (when it is differentiable) is increasing.
Proof
The first two properties follow easily from the definitions. We prove Property 3; the proof of Property 4 is similar. Since \(h(x)\) is monotone, \(h(w(j,i))\) remains monotone under interval inclusion. The quadrangle inequality is the crux.
To prove it, consider the mixed second difference over \(a \leq j \leq b \leq c \leq i \leq d\).
Here, by monotonicity under interval inclusion, \(\Delta_iw(a,i) := w(a,d) - w(a,c) \geq 0\) and \(\Delta_jw(j,c) := w(b,c) - w(a,c) \leq 0\). Since \(h(x)\) is convex, \(h(x + t_1 - t_2) - h(x + t_1) \leq h(x - t_2) - h(x)\) for \(t_1,t_2\geq 0\), so the sum of the last two lines is non-positive. By the quadrangle inequality, \(w(b,d) \leq w(a,c) + \Delta_jw(j,c) + \Delta_iw(a,i) = w(b,c) + w(a,d) - w(a,c)\), so the difference in the first line is also non-positive since \(h(x)\) is increasing. Hence the whole mixed second difference is non-positive, which is the quadrangle inequality.
This proof is in fact a discrete version of the following proof by derivatives.
This clearly holds when \(h' \geq 0\), \(h'' \geq 0\), \(w_x \leq 0\), \(w_y \geq 0\) and \(w_{xy} \leq 0\). Here monotonicity under interval inclusion gives the first-order conditions on \(w\), and the quadrangle inequality gives the second-order condition.
Practice problems
- Codeforces - Ciel and Gondolas(Be careful with I/O!)
- SPOJ - LARMY
- Codechef - CHEFAOR
- Hackerrank - Guardians of the Lunatics
- ACM ICPC World Finals 2017 - Money
References and notes
- Quora Answer by Michael Levin
- Video Tutorial by "Sothe" the Algorithm Wolf
- Divide and Conquer DP
- Knuth's Optimization
- Quadrangle Inequality Properties
- Qinshi Wang, On a Class of Binary-Search Methods (in Chinese)
- Simplified LARSCH Algorithm by noshi91 (in Japanese)
- The Quadrangle Inequality and Decision Monotonicity by b6e0_ - Luogu article (in Chinese)
- A Poor Man's LARSCH Algorithm for Online Decision Monotonicity by Register_int - Luogu article (in Chinese)
-
In the description of the algorithm, "worse" and "better" refer to the lexicographical order that compares function values first and decision points second. In this order, "better" means either a smaller function value, or the same function value and a smaller decision point. ↩
-
Larmore, Lawrence L., and Baruch Schieber. "On-line dynamic programming with applications to the prediction of RNA secondary structure." Journal of Algorithms 12, no. 3 (1991): 490-515. ↩
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: Marcythm, zyf0726, hsfzLZH1, MingqiHuang, Ir1d, greyqz, billchenchina, Chrogeek, StudyingFather, NFLSCode, c-forrest, Xeonacid, 24OI-bot, ouuan, zryi2003, Henry-ZHR, sshwy, Yanjun-Zhao, nanmenyangde, Elitedj, izlyforever, Enter-tainer, ranwen, opsiff, iamtwz, ksyx, NachtgeistW, Menci, CCXXXI, shawlleyw, Tiphereth-A, chang-wenxuan, TOMWT-qwq, HeRaNO, Plastic-time (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.