Quadrangle Inequality Optimization

Quadrangle inequality optimization utilizes the monotonicity in the state transition equation, often referred to as DP optimization with decision monotonicity.

Fundamentals

Consider the simplest scenario: we need to solve the following series of optimization problems:

\[ f(i) = \min_{1 \leq j \leq i} w(j,i) \qquad \left(1 \leq i \leq n\right) \tag{1} \]

Here, we assume the cost function \(w(j,i)\) can be computed in \(O(1)\) time.

Convention

The state transition equations in dynamic programming can often be written as a series of optimization problems. Taking equation (1) as an example, these problems have a parameter \(i\), and both the objective function and the feasible set can depend on \(i\). Each problem, given parameter \(i\), selects a feasible solution \(j\) to minimize the value of the objective function. For convenience, the optimization problem with parameter \(i\) is referred to as "problem \(i\)", the feasible solution \(j\) for this optimization problem is called "decision \(j\)", and the value of the objective function at the optimal solution is called "state \(f(i)\)". Additionally, denote the minimum optimal decision point for problem \(i\) as \(\operatorname{opt}(i)\).

In the general case, the total time complexity of these problems is \(O(n^2)\). This is because for problem \(i\), we need to consider all possible decisions \(j\). When decision monotonicity holds, the decision space can be effectively reduced, optimizing the total complexity.

Decision Monotonicity: For any \(i_1 < i_2\), it must hold that \(\operatorname{opt}(i_1) \leq \operatorname{opt}(i_2)\).

Note

For problem \(i\), the set of optimal decisions is not necessarily an interval. Decision monotonicity can actually be defined on the set of optimal decisions. For sets \(A\) and \(B\), we can define \(A \leq B\) if and only if for any \(a\in A\) and \(b\in B\), \(\min\{a,b\}\in A\) and \(\max\{a,b\}\in B\) hold. This implies the monotonicity of the minimum (maximum) optimal decision point, which is the definition adopted here. The conclusions stated in this article regarding the minimum optimal decision point also apply to the maximum optimal decision point. However, there are cases where the minimum optimal decision of a larger problem is strictly less than the maximum optimal decision of a smaller problem, i.e., it is possible that for some \(i_1 < i_2\), \(\mathop{\mathrm{optmax}}(i_1) > \mathop{\mathrm{optmin}}(i_2)\) holds. Therefore, when writing code, ensure that you always compute either the minimum or the maximum optimal decision point.

On the other hand, problems with the same minimum optimal decision form an interval. This interval, as a function of the minimum optimal decision, should be strictly increasing. That is, given \(j_1 = \operatorname{opt}(i_1)\), \(j_2 = \operatorname{opt}(i_2)\), if \(j_1 < j_2\), then it must be that \(i_1 < i_2\). In other words, if the problem intervals where decisions \(j_1 < j_2\) can be the minimum optimal decision are \([l_{j_1},r_{j_1}]\) and \([l_{j_2},r_{j_2}]\) respectively, then it must hold that \(r_{j_1} < l_{j_2}\).

The most common method to determine decision monotonicity is through the quadrangle inequality. In different contexts, this property is also called the Monge property (used to describe the matrix \(A_{j,i}\)) or submodularity (used to describe the function \(f([j,i])\) with intervals as arguments).

Quadrangle Inequality: If for any \(a\leq b\leq c\leq d\), the following holds:

\[ w(a,c)+w(b,d) \leq w(a,d)+w(b,c), \]

then the function \(w\) is said to satisfy the quadrangle inequality (abbreviated as "cross less than contain"). If equality always holds, then \(w\) is said to satisfy the quadrangle identity.

Unless otherwise specified, we always assume \(a\leq b\leq c\leq d\). The quadrangle inequality provides a sufficient but not necessary condition for decision monotonicity.

Theorem 1

If \(w\) satisfies the quadrangle inequality, then problem (1) satisfies decision monotonicity.

Proof

To prove this, we use proof by contradiction. Suppose for some \(c < d\), we have \(a = \operatorname{opt}(d) < \operatorname{opt}(c) = b\). Then \(a < b \leq c < d\). By the optimality condition, \(w(a,d) \leq w(b,d)\) and \(w(b,c) < w(a,c)\). Thus, \(w(a,d) - w(b,d) \leq 0 < w(a,c) - w(b,c)\), which contradicts the quadrangle inequality.

The quadrangle inequality can be understood as the second-order mixed difference \(\Delta_i\Delta_jw(j,i)\) of \(w\) being non-positive over a reasonable domain.

Using decision monotonicity, many common algorithms can optimize the complexity to \(O(n\log n)\). The applicability, implementation difficulty, and runtime efficiency of these algorithms vary, and the appropriate algorithm should be chosen based on the actual scenario. This mainly depends on the properties of \(w(j,i)\). Unless stated otherwise, this article assumes \(w(i,j)\) can be randomly accessed, meaning \(w(j,i)\) can be queried or computed in \(O(1)\) time. However, not all problems have \(w(j,i)\) that is easy to compute. Therefore, besides the basic case, this article also discusses methods to optimize DP with decision monotonicity when \(w(j,i)\) only has the following properties:

Move Access: \(w(j,i)\) can be transferred from \(w(j\pm 1,i)\) or \(w(j,i\pm 1)\) in \(O(1)\) time. (Similar to the situation in Mo's algorithm)
Dynamic Computation: The computation of \(w(j,i)\) depends on \(\{f(j'):j' < j\}\). This means \(f\) and \(w\) can only be computed sequentially. The interval partition problem with an unlimited number of intervals discussed later belongs to this category.

These two properties are not mutually exclusive; there may be cases where \(w(j,i)\) requires both dynamic computation and only supports move access.

Divide and Conquer

To solve all states, we only need to solve for all optimal decision points. To solve for \(\operatorname{opt}(i)\) for all \(1 \leq i \leq n\), first compute \(\operatorname{opt}(n/2)\), then compute \(\operatorname{opt}(i)\) for \(1 \leq i < n/2\) and \(n/2 < i \leq n\) separately. Note that now we know that \(\operatorname{opt}(i)\) for the first half must lie between \(1\) and \(\operatorname{opt}(n/2)\) (inclusive), and \(\operatorname{opt}(i)\) for the second half must lie between \(\operatorname{opt}(n/2)\) and \(n\) (inclusive). Process the two subintervals similarly until the optimal decision for each problem is computed. By recording the search boundaries during the divide and conquer process, the algorithm complexity can be controlled at \(O(n\log n)\). The recursion tree has \(O(\log n)\) layers, and in each layer, each decision point is computed at most twice, so the total number of computations is \(O(n\log n)\).

Reference Implementation

val_t w(int j, int i);  // Cost function
val_t f[N];             // Optimal value
int opt[N];             // Minimum optimal decision

// Recursively solve problems in [l, r]
// It is known that their minimum optimal decision points must lie within the interval [opt_l, opt_r]
void calc(int l, int r, int opt_l, int opt_r) {
  int mid = (l + r) / 2;
  // Find the optimal decision point for problem mid
  for (int j = opt_l; j <= std::min(opt_r, mid); ++j) {
    if (w(j, mid) < f[mid]) {
      f[mid] = w(j, mid);
      opt[mid] = j;
    }
  }
  // Based on decision monotonicity, determine the decision intervals for the left and right parts, and process recursively
  if (l < mid) calc(l, mid - 1, opt_l, opt[mid]);
  if (r > mid) calc(mid + 1, r, opt[mid], opt_r);
}

// Solve the entire interval [1, n]
void solve(int n) {
  // Before each call to the recursive function, the array f must be cleared
  std::fill(f + 1, f + n + 1, inf);
  // Initially, it is only known that all decision points for problems [1, n] must lie within [1, n]
  calc(1, n, 1, n);
}

Besides the basic case of random access, the divide and conquer algorithm can also be applied when \(w(j,i)\) only supports move access. It is sufficient to maintain the cursor \((j,i)\) and the corresponding function value \(w(j,i)\) during computation. When a new value needs to be queried, brute-force move the cursor to the current position and update the function value. The time complexity remains \(O(n\log n)\). For a more detailed discussion on this, refer to the section Simplified LARSCH Algorithm below. However, the divide and conquer algorithm cannot handle the case where \(w(j,i)\) requires dynamic computation, because the divide and conquer algorithm cannot compute the minimum optimal decision \(\operatorname{opt}(n/2)\) at the midpoint before the left half problems are solved.

Binary Queue

Note that for each decision point \(j\), the problems \(i\) for which \(j\) can be the minimum optimal decision point must form an interval. A monotonic queue can be used to record the interval of problems that each decision point can solve so far. Then, the optimal solution for a problem can naturally be computed using the decision points recorded in the queue.

Specifically, the algorithm needs to traverse decision points sequentially. When traversing to decision point \(k\), the queue needs to record each feasible decision point \(j\) so far and the left and right endpoints \(l_j\) and \(r_j\) of the problem interval it can solve, forming a triple. For problems in the given interval \([l_j,r_j]\), \(j\) should be the minimum optimal decision among the decision points considered so far (i.e., decision points in the interval \([1,k]\)). At any moment, the decisions stored in the queue may not be consecutive, but the unsolved problems \([j,n]\) should be a disjoint union of the problem intervals stored in the queue.

To illustrate that during queue updates, the problems \(i\) for which decision point \(j\) is the minimum optimal decision always form a continuous interval, we need to appropriately strengthen the previous conclusion:

Corollary 1

Let \(\operatorname{opt}_k(i)\) be the minimum optimal decision for problem \(i\) when only considering decisions in \([1,k]\). If \(w\) satisfies the quadrangle inequality, then for any \(i_1 < i_2\), it must hold that \(\operatorname{opt}_k(i_1) \leq \operatorname{opt}_k(i_2)\).

Proof

Let \(M\) be a sufficiently large positive real number. The function \(w'(j,i) = w(j,i) + M[j > k]\) still satisfies the quadrangle inequality, where \([\cdot]\) is the Iverson bracket. Consider an auxiliary DP with cost function \(w'\). In the auxiliary DP, for any problem \(i\), decision \(j > k\) cannot be the minimum optimal, i.e., \(\operatorname{opt}'(i) = \operatorname{opt}'_k(i) = \operatorname{opt}_k(i)\). Applying Theorem 1 to the auxiliary DP yields this corollary.

The algorithm process is as follows:[^cmp-min-opt]

Initially, the queue is empty. Similar to a monotonic queue, each time the next decision \(j\) is considered, dequeue and enqueue operations are required.
Dequeue: First, remove the previous problem \(j-1\) from the queue. If the right endpoint of the problem that the head decision can solve is exactly \(j-1\), pop the head directly; otherwise, update the left endpoint of the problem that the head decision can solve to \(j\).
Enqueue: When enqueuing decision \(j\), first compare it with the tail decision \(j'\).
- If for problem \(l_{j'}\), the decision \(j\) to be enqueued is strictly better than the existing decision \(j'\), i.e., \(w(j,l_{j'}) < w(j',l_{j'})\), then pop the tail decision \(j'\). This operation continues until the queue is empty or the tail decision \(j'\) is better than \(j\) for problem \(l_{j'}\).
- If the queue becomes empty, enqueue \((j,j,n)\), meaning decision \(j\) is the optimal solution for all unsolved problems.
- If the tail decision \(j'\) is not worse than the decision \(j\) to be enqueued for problem \(r_{j'}\) as well, then when \(r_{j'} < n\), enqueue \((j,r_{j'}+1,n)\), indicating that \(j\) is the minimum optimal decision for problems \([r_{j'}+1,n]\); otherwise, do not enqueue \(j\) because it is not better than the existing decision.
- The final case is that the tail decision \(j'\) is strictly better than the decision \(j\) to be enqueued for problem \(l_{j'}\), but strictly worse for problem \(r_{j'}\). This indicates that there exists a problem \(i\in(l_{j'},r_{j'}]\) such that the minimum optimal decision for problems \([l_{j'},i-1]\) is \(j'\) and for problems \([i,r_{j'}]\) is \(j\). Therefore, we need to binary search for the smallest \(i\in[l_{j'},r_{j'}]\) such that \(w(j,i) < w(j',i)\), then modify the tail interval's right endpoint \(r_{j'}\) to \(i-1\), and enqueue \((j,i,n)\).
After processing decision \(j\), all decisions up to \(j\) have been processed. At this point, the head decision is the minimum optimal decision for problem \(j\), and the corresponding optimal solution can be recorded.

Reference Implementation

val_t w(int j, int i);  // Cost function
val_t f[N];             // Optimal value
int opt[N];             // Minimum optimal decision
int lt[N], rt[N];       // The interval of problems that decision j can solve: [l_j, r_j]

// Solve the entire interval [1, n]
void solve(int n) {
  std::deque<int> dq;  // Monotonic queue storing all feasible decisions

  // Consider all problems and decisions sequentially, indices start from 1
  for (int j = 1; j <= n; ++j) {
    // Dequeue
    if (!dq.empty() && rt[dq.front()] < j) dq.pop_front();
    if (!dq.empty()) lt[dq.front()] = j;
    // Enqueue
    while (!dq.empty() && w(j, lt[dq.back()]) < w(dq.back(), lt[dq.back()])) {
      dq.pop_back();
    }
    if (dq.empty()) {
      lt[j] = j;
      rt[j] = n;
      dq.emplace_back(j);
    } else if (w(j, rt[dq.back()]) >= w(dq.back(), rt[dq.back()])) {
      if (rt[dq.back()] < n) {
        lt[j] = rt[dq.back()] + 1;
        rt[j] = n;
        dq.emplace_back(j);
      }
    } else {
      int ll = lt[dq.back()], rr = rt[dq.back()], i = rr;
      // Binary search
      while (ll <= rr) {
        int mm = (ll + rr) / 2;
        if (w(j, mm) < w(dq.back(), mm)) {
          i = mm;
          rr = mm - 1;
        } else {
          ll = mm + 1;
        }
      }
      rt[dq.back()] = i - 1;
      lt[j] = i;
      rt[j] = n;
      dq.emplace_back(j);
    }
    // Calculate
    f[j] = w(dq.front(), j);
    opt[j] = dq.front();
  }
}

Similar to a monotonic queue, each decision point is enqueued at most once and dequeued at most once. Dequeue is \(O(1)\), while enqueue is \(O(\log n)\) (may require binary search), so the total time complexity is \(O(n\log n)\).

Since the binary queue algorithm considers all problems and decision points sequentially, it can be applied when \(w(j,i)\) requires dynamic computation. This is its advantage over the divide and conquer algorithm. However, because the binary search step in the algorithm relies on random access to \(w(j,i)\), it cannot be applied when \(w(j,i)\) only supports move access.

Example 1: 「POI2011」Lightning Conductor

Given a sequence \(a_1,a_2,\cdots,a_n\) of length \(n\), for each \(1 \leq i \leq n\), find the smallest non-negative integer \(f_i\) such that

\[ \forall j\in\left[1,n\right]:a_j \leq a_i + f_i - \sqrt{|i-j|}. \]

Idea

Clearly, after inequality transformation, we obtain the desired integer \(f_i = \max_{j}\{a_j+\sqrt{|i-j|}-a_i\}\). Consider the case \(j \leq i\) first (the other case is similar), then we have the state transition equation:

\[ f_i = -\min_{j\le i}\{-a_j-\sqrt{i-j}+a_i\}. \]

Based on the convexity of \(-\sqrt{x}\), we can easily deduce (detailed later) that the function \(w(l, r) = -a_l - \sqrt{r-l} + a_r\) satisfies the quadrangle inequality. Therefore, applying the above algorithm can solve this problem in \(O(n\log n)\) time.

Implementation

#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#define all \
  for (auto i : {&q, &l, &r}) (*i)
using namespace std;
int n, a[500009], ans[500009];
deque<int> q, l, r;

double f(int i, int j) { return a[i] + sqrtl(j - i); }

void work() {
  all.clear();
  for (int i = 0; i < n; ++i) {
    if (q.size() && r.front() < i) all.pop_front();  // Dequeue from front
    if (q.size()) l.front() = i;
    for (; q.size() && f(q.back(), l.back()) <= f(i, l.back());)  // Dequeue from back
      all.pop_back();
    if (q.empty())  // Enqueue
      q.emplace_back(i), l.emplace_back(i), r.emplace_back(n);
    else if (f(q.back(), n) < f(i, n)) {
      int ll = l.back(), rr = n, mid;
      for (; ll <= rr;) {
        mid = (ll + rr) >> 1;
        if (f(q.back(), mid) < f(i, mid))
          rr = mid - 1;
        else
          ll = mid + 1;
      }
      r.back() = rr;
      q.emplace_back(i), l.emplace_back(ll), r.emplace_back(n);
    }
    ans[i] = max(ans[i], (int)(ceil(f(q.front(), i))) - a[i]);
  }
}

int main() {
  cin >> n;
  for (int i = 0; i < n; cin >> a[i++]);
  work();
  reverse(a, a + n);
  reverse(ans, ans + n);
  work();
  reverse(ans, ans + n);
  for (int i = 0; i < n; cout << ans[i++] << '\n');
}

Simplified LARSCH Algorithm

The previous two algorithms cannot handle the case where \(w(j,i)\) requires both dynamic computation and only supports move access. This section introduces an algorithm that can overcome both difficulties simultaneously. It is a simplified version of the LARSCH algorithm proposed by Larmore and Schieber in 1991[^larsch], hence called the Simplified LARSCH Algorithm. The original version of this algorithm can solve DP problems with decision monotonicity in \(O(n)\) time, but its implementation is more complex and is not covered here.

Still consider solving by divide and conquer. When solving problems in the interval \((l,r]\), assume the following information is known:

The minimum optimal decision \(\operatorname{opt}(i)\) and optimal value for problems \(i\) in the interval \([1,l]\), and
The minimum optimal decision \(\operatorname{opt}_l(r)\) and optimal value for problem \(r\) when only considering decisions in the interval \([1,l]\).

After solving problems in the interval \((l,r]\), we need to obtain the minimum optimal decisions and optimal values for problems in \((l,r]\).

Let \(\textit{mid}\) be the midpoint of the interval \((l,r]\). The solving process is as follows:

Traverse decisions \(i\in[\operatorname{opt}(l),\operatorname{opt}_l(r)]\), update the minimum optimal decision and optimal value for problem \(\textit{mid}\).
Recursively solve problems in the interval \((l,\textit{mid}]\).
Traverse decisions \(i\in(l,\textit{mid}]\), update the minimum optimal decision and optimal value for problem \(r\).
Recursively solve problems in the interval \((\textit{mid},r]\).

Before performing recursion on the entire interval \([1,n]\), first use decision \(j=1\) to update problems \(i\in\{1,n\}\). The algorithm terminates when \(l=r\) in recursion.

Reference Implementation

val_t w(int j, int i);  // Cost function
val_t f[N];             // Optimal value
int opt[N];             // Minimum optimal decision

// Update problem i with decision j
void check(int j, int i) {
  if (w(j, i) < f[i]) {
    f[i] = w(j, i);
    opt[i] = j;
  }
}

// Recursively solve problems in interval (l, r]
void calc(int l, int r) {
  int mid = (l + r + 1) / 2;
  for (int j = opt[l]; j <= opt[r]; ++j) check(j, mid);
  if (mid < r) calc(l, mid);
  for (int j = l + 1; j <= mid; ++j) check(j, r);
  if (mid > l) calc(mid, r);
}

// Solve all problems in interval [1, n]
void solve(int n) {
  // Clear f array
  std::fill(f + 1, f + n + 1, inf);
  // Initialize
  check(1, 1);
  check(1, n);
  // Recursively solve problems in interval (1, n]
  calc(1, n);
}

First, we can justify the correctness of this algorithm. For this, it suffices to check that the preconditions given above are satisfied before each recursive solving step (i.e., steps 2 and 4). By Corollary 1 from the previous section, we have \(\operatorname{opt}(l)=\operatorname{opt}_l(l)\le\operatorname{opt}_l(\textit{mid})\le\operatorname{opt}_l(r)\). So after step 1, \(\operatorname{opt}_l(\textit{mid})\) is known, and thus the precondition for recursively solving problems in \((l,\textit{mid}]\) before step 2 holds. Since \(\{\operatorname{opt}(i):i\in[1,l]\}\) was known before, and step 2 obtains the values of \(\{\operatorname{opt}(i):i\in(l,\textit{mid}]\}\), after that, \(\{\operatorname{opt}(i):i\in[1,\textit{mid}]\}\) are all known; meanwhile, since \(\operatorname{opt}_l(r)\) was known before, after step 3, \(\operatorname{opt}_\textit{mid}(r)\) is also known. Therefore, the precondition for recursively solving problems in \((\textit{mid},r]\) before step 4 also holds.

Next, we need to show that the complexity of this algorithm is still \(O(n\log n)\). The recursion tree has \(O(\log n)\) layers. For each node in the same layer of the recursion tree, we traverse decisions in the intervals \([\operatorname{opt}(l),\operatorname{opt}_l(r)]\) and \((l,\textit{mid}]\) respectively. Since \(\operatorname{opt}(l)\le\operatorname{opt}_l(r)\le\operatorname{opt}(r)\), in the same layer, each decision point is traversed \(O(1)\) times. Hence, the total number of traversals in each layer of the recursion tree is \(O(n)\). Assuming a single access or computation of \(w(j,i)\) takes \(O(1)\) time, the algorithm's time complexity is \(O(n\log n)\).

For some cases where \(w(j,i)\) only supports move access, the complexity of this algorithm remains \(O(n\log n)\). In such cases, we need to maintain the current values of the cursor \((j,i)\) and \(w(j,i)\) for steps 1 and 3 in the algorithm flow separately. Each time a new value needs to be accessed, the cursor \((j,i)\) needs to be brute-force updated from its previous position to the current position, and the function value \(w(j,i)\) is transferred accordingly. It can be verified that when traversing the recursion tree, the total number of such brute-force updates is \(O(n\log n)\). Therefore, the algorithm's time complexity remains \(O(n\log n)\).

Complexity Proof for Non-Random Access

We only need to prove that the total number of cursor moves is \(O(n\log n)\). Let \(A\) and \(B\) be the cursors corresponding to steps 1 and 3, respectively. In fact, it can be guaranteed that before solving problems in the interval \((l,r]\), cursor \(A\) is at position \((\operatorname{opt}(l),l)\), and cursor \(B\) is at position \((l,l)\); after that, cursor \(A\) is at position \((\operatorname{opt}(r),r)\), and cursor \(B\) is at position \((r,r)\).

Consider constructing the following cursor movement rules. In step 1, let cursor \(A\) move along the path

\[ (\operatorname{opt}(l),l)\to(\operatorname{opt}(l),\textit{mid})\to(\operatorname{opt}_l(r),\textit{mid})\to(\operatorname{opt}(l),\textit{mid})\to(\operatorname{opt}(l),l) \]

At this point, cursors \(A\) and \(B\) are at the required positions before solving problems in \((l,\textit{mid}]\). In step 2, as required, cursor \(A\) will move to \((\operatorname{opt}(\textit{mid}),\textit{mid})\), and cursor \(B\) will move to \((\textit{mid},\textit{mid})\). In step 3, let cursor \(B\) move along the path

\[ (\textit{mid},\textit{mid}) \to (l,\textit{mid}) \to (l, r) \to (\textit{mid},r) \to (\textit{mid},\textit{mid}) \]

At this point, cursors \(A\) and \(B\) are at the required positions before solving problems in \((\textit{mid},r]\). In step 4, as required, cursor \(A\) will move to \((\operatorname{opt}(r),r)\), and cursor \(B\) will move to \((r,r)\). Both cursors are at the required positions after solving problems in \((l,r]\). Therefore, this movement rule complies with the above requirements. Moreover, this movement rule is sufficient to perform all computations in steps 1 and 3. Directly calculating the number of moves in this rule shows that step 1 requires

\[ 2(\operatorname{opt}_l(r) - \operatorname{opt}(l)) + 2(\textit{mid} - l) \]

moves, and step 3 requires

\[ 2(\textit{mid}-l)+2(r-\textit{mid}) = 2(r-l) \]

moves. Summing these move counts over all nodes in the recursion tree, and using the property that all \([l,r]\) and \([\operatorname{opt}(l),\operatorname{opt}_l(r)]\) in the same layer overlap at most at endpoints, we can conclude that the total number of moves is \(O(n\log n)\).

Since the above movement rule sets more waypoints than the actual cursor movement during computation, the actual number of cursor moves will not exceed the estimate under this rule. Therefore, the actual number of cursor moves is also \(O(n\log n)\).

Since this algorithm has already computed the optimal solutions \(f(i)\) for the interval \([1,l]\) before solving problems in \((l,r]\), it can also be applied when \(w(j,i)\) requires dynamic computation.

Interval Partition Problems

Consider the problem of partitioning a given interval into several subintervals. Formally, partition 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}\) holds for any \(i < k\). For a given partition, the cost is \(\sum_{i=1}^kw(a_i,b_i)\). The problem asks to minimize this cost. The following 1D1D state transition equation can be written:

\[ f(i) = \min_{1\leq j\leq i} f(j-1)+w(j,i) \qquad (1\leq i\leq n) \]

Here, \(f(0)=0\). Note that as long as \(w(j,i)\) satisfies the quadrangle inequality, \(f(j-1)+w(j,i)\) must satisfy the quadrangle inequality because the first term does not include cross terms of \(j\) and \(i\), which cancel out in mixed differences. However, since the cost function depends on previous subproblems, this transition can only be computed sequentially, so the first divide and conquer algorithm described earlier cannot be applied. Usually, only the binary queue algorithm or the simplified LARSCH algorithm is suitable. The algorithm complexity is \(O(n\log n)\).

Case with Limited Number of Intervals

The above problem can be strengthened to the case where the number of intervals is limited, i.e., the problem specifies that the interval is to be partitioned into \(m\) subintervals. In this case, the number of intervals after partitioning needs to be included as a dimension of the state. Correspondingly, we have the following 2D1D state transition equation:

\[ f(k,i) = \min_{1\leq j\leq i} f(k-1,j-1)+w(j,i) \qquad (1\leq k\leq m,\ 1\leq i\leq n) \tag{2} \]

Here, \(f(0,0)=0\), and \(f(0,i)=f(k,0)=\infty\) for any \(1\leq k\leq m\) and \(1\leq i\leq n\). For the same reason as above, \(f(k-1,j-1)+w(j,i)\) here must satisfy the quadrangle inequality. Now, the computation for the \(i\)-th layer no longer depends on the results of this layer, so for each layer, any algorithm described in the previous section can be used for computation, resulting in an algorithm complexity of \(O(mn\log n)\).

For this problem, utilizing decision monotonicity, there are actually other optimization algorithms. The second optimization approach relies on the following result. This optimization algorithm is very similar to the Knuth optimization algorithm described in detail later.

Theorem 2

If \(w\) satisfies the quadrangle inequality, then for problem (2), \(\operatorname{opt}(k-1,i) \leq \operatorname{opt}(k,i) \leq \operatorname{opt}(k,i+1)\) holds.

Proof

The second inequality is just the decision monotonicity of the \(k\)-th layer. The key is the first inequality.

We prove \(\operatorname{opt}(k,i) \leq \operatorname{opt}(k+1,i)\). Suppose we have two partitions of \([1,i]\) (labeled in reverse order): \([a_{k},d_{k}],\cdots,[a_1,d_1]\) and \([b_{k+1},c_{k+1}],\cdots,[b_1,c_1]\). Here, the left endpoint of each interval is the minimum optimal decision for the problem at its right endpoint; similarly, considering all possible partitions from right to left, the right endpoint is also the minimum optimal decision for the problem at its left endpoint. For example, \(d_j\) and \(c_j\) are the minimum optimal decisions for the right endpoint of the first interval from the left when partitioning \([a_j,i]\) and \([b_j,i]\) into \(j\) segments, respectively. By decision monotonicity, if \(a_{j-1} > b_{j-1}\), i.e., \(d_j > c_j\), then it must be that \(a_j > b_j\). Thus, if the statement to be proved does not hold, we have \(a_1 > b_1\). Then we can inductively prove \(a_{k} > b_{k}\). This clearly contradicts the assumption. Hence the statement is proved.

The first inequality can also be proved as follows. Consider the same two partitions as in the above proof. If the statement does not hold, we have \(a_1 > b_1\), but since \(a_{k} < b_{k}\), we can find the smallest \(j>1\) such that \(a_j \leq b_j\). Then, we have \(a_{j-1} > b_{j-1}\), so \(d_j>c_j\). We have found a set of intervals satisfying \(a_j \leq b_j \leq c_j < d_j\). Consider recombining these two partitions. Consider 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]\), totaling \((k+1)\) segments. Then by the assumed optimality, we have

\[ \begin{aligned} &w(b_{k+1},c_{k+1})+\cdots+w(b_{j+1},c_{j+1})+w(b_j,c_j)+w(b_{j-1},c_{j-1})+\cdots+w(b_1,c_1) \\ &\qquad \leq w(b_{k+1},c_{k+1})+\cdots+w(b_{j+1},c_{j+1})+w(b_j,d_j)+w(a_{j-1},d_{j-1})+\cdots+w(a_1,d_1). \end{aligned} \]

Similarly, consider 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]\), totaling \(k\) segments, then

\[ \begin{aligned} &w(a_{k},d_{k})+\cdots+w(a_{j+1},d_{j+1})+w(a_j,d_j)+w(a_{j-1},d_{j-1})+\cdots+w(a_1,d_1) \\ &\qquad < w(a_{k},d_{k})+\cdots+w(a_{j+1},d_{j+1})+w(a_j,c_j)+w(b_{j-1},c_{j-1})+\cdots+w(b_1,c_1). \end{aligned} \]

Here, the inequality is strict because \(a_1 > b_1\), but by assumption, \(a_1\) is the minimum optimal among all left endpoints of the last segment in \(k\)-segment partitions. Adding the two inequality conditions, we get \(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. Hence the original conclusion is proved.

Using this result, we can limit the search range for decision \(j\). When implementing the algorithm, traverse \(k\) forward and \(i\) backward, and brute-force search \(j\) within the previously determined upper and lower bounds. This ensures an algorithm complexity of \(O(n(n+m))\).

Note

The algorithm complexity here is not \(O(nm)\). The correct complexity calculation needs to consider the \(n\times m\) state matrix. Because for problem \((i,k)\), we only need to consider decisions in \(\operatorname{opt}(k-1,i) \leq j \leq \operatorname{opt}(k,i+1)\), the total number of decisions traversed for problems on each anti-diagonal (i.e., where \(i-k\) is constant) is \(O(n)\). There are \((n+m)\) such diagonals in total, so the total time complexity is \(O(n(n+m))\).

The last optimization method comes from the following observation.

Theorem 3

If \(w\) satisfies the quadrangle inequality, then the optimal solution \(g(k):=f(n,k)\) of problem (2) is a convex function of \(k\).

Proof

We prove \(g(k-1) + g(k+1) \ge 2g(k)\). For this, consider the optimal partitions of lengths \((k-1)\) and \((k+1)\) segments, respectively: \([a_1,d_1],\cdots,[a_{k-1},d_{k-1}]\) and \([b_1,c_1],\cdots,[b_{k+1},c_{k+1}]\). Take the smallest \(1 \leq j \leq k-1\) such that \(c_{j+1} \leq d_j\), whose existence is implied by \(c_{k} < n = d_{k-1}\). By its minimality, \(b_{j+1} > a_j\). So, \(a_j < b_{j+1} \leq c_{j+1} \leq d_j\). Similar to above, swapping the latter halves of the two existing partitions, we obtain the following two interval partitions:

\[ \begin{aligned} & [a_1,d_1],\cdots,[a_{j-1},d_{j-1}],[a_j,c_{j+1}],[b_{j+2},c_{j+2}],\cdots,[b_{k+1},c_{k+1}], \\ & [b_1,c_1],\cdots,[b_j,c_j],[b_{j+1},d_j],[a_{j+1},d_{j+1}],\cdots,[a_{k-1},d_{k-1}]. \end{aligned} \]

Both resulting partitions have \(k\) segments, so by the optimality condition,

\[ \begin{aligned} 2g(k) &\le w(a_1,d_1) + \cdots + w(a_{j-1},d_{j-1}) + w(a_j,c_{j+1}) + w(b_{j+2},c_{j+2}) + \cdots + w(b_{k+1},c_{k+1}) \\ &\quad + w(b_1,c_1) + \cdots + w(b_j,c_j) + w(b_{j+1},d_j) + w(a_{j+1},d_{j+1}) + \cdots + w(a_{k-1},d_{k-1}) \\ &\le w(a_1,d_1) + \cdots + w(a_{j-1},d_{j-1}) + w(a_j,d_j) + w(a_{j+1},d_{j+1}) + \cdots + w(a_{k-1},d_{k-1}) \\ &\quad + w(b_1,c_1) + \cdots + w(b_j,c_j) + w(b_{j+1},c_{j+1}) + w(b_{j+2},c_{j+2}) + \cdots + w(b_{k+1},c_{k+1}) \\ &= g(k-1) + g(k+1). \end{aligned} \]

The second inequality here is exactly the quadrangle inequality. The desired convexity follows.

This conclusion ensures that this problem can be solved using WQS binary search (also known as Aliens Trick). Specifically, consider the parameterized cost function \(w_c(j,i):=w(j,i)+c\), solve the problem without limiting the number of intervals, and obtain its optimal solution as \(f_c(n)\). As the real number \(c\) increases, the corresponding optimal number of intervals decreases monotonically. Therefore, we can use binary search to find the parameter \(c\) such that the optimal number of intervals equals \(m\). Then the original optimal solution is \(f(n,m) = f_c(n)-cm\). Here, the real number \(c\) can be seen as a Lagrange multiplier for the interval count constraint. There are many implementation details for this algorithm; refer to the WQS Binary Search page. The time complexity of this algorithm is \(O(n\log n\log C)\), where \(C\) is some constant.

For the three algorithms for the interval partition problem with a limited number of intervals, their performance varies under different data ranges. The appropriate algorithm should be chosen based on the specific problem.

Example 3: P4767 [IOI2000] Post Office Enhanced P6246 [IOI2000] Post Office Enhanced Enhanced

There are some villages along a highway. The highway is represented as an integer axis, and the position of each village is identified by a single integer coordinate. No two villages are in the same place. 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, villages. To establish post offices, their locations should be chosen so that the total distance

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用