1. Formal Invariant — Convexity & Supporting Hyperplanes
Invariant: Lagrangian Duality on Discrete Convex Functions
Let $f(k)$ be the minimum cost to solve a problem using exactly $k$ items/segments. We say $f(k)$ is convex on $k \in [0, N]$ if its discrete first differences (marginal costs) $\Delta(k) = f(k) - f(k-1)$ are non-decreasing:
$$f(k) - f(k-1) \le f(k+1) - f(k) \quad \forall\, 1 \le k < N$$
For any penalty parameter $\lambda \in \mathbb{R}$, define the penalized unconstrained problem:
$$g(\lambda) = \min_{0 \le k \le N} \Big( f(k) + \lambda \cdot k \Big)$$
Because $f(k)$ is convex, the set of minimizers $\arg\min_k (f(k) + \lambda k)$ forms a contiguous interval $[k_{\min}(\lambda),\; k_{\max}(\lambda)]$, and increasing $\lambda$ monotonically decreases $k(\lambda)$. If we binary search $\lambda^*$ such that $K \in [k_{\min}(\lambda^*),\; k_{\max}(\lambda^*)]$, then:
$$f(K) = g(\lambda^*) - \lambda^* \cdot K$$
2. Geometric Tangent Interpretation & Collinear Tie-Breaking
Record (min_cost, min_count)"] SolveUnconstrained -->|"count > K (too cheap)"| IncreaseLambda["Increase lambda"] SolveUnconstrained -->|"count <= K"| DecreaseLambda["Decrease lambda & Save Answer"] end
What if multiple points $(k-1, f(k-1)), (k, f(k)), (k+1, f(k+1))$ are collinear on the convex hull? At the exact tangent slope $\lambda^*$, all of them achieve the exact same penalized objective $f(k) + \lambda^* k = g(\lambda^*)$! If we consistently break ties in the 1D DP by choosing the minimum segment count cnt whenever penalized costs are equal, and we binary search for the largest $\lambda^*$ where cnt <= K (or smallest $\lambda^*$ where cnt <= K depending on tie-breaking), then even if $k(\lambda^*)$ jumps across the collinear flat spot from $k_{\min} \le K$ to $k_{\max} \ge K$, the formula $g(\lambda^*) - \lambda^* \cdot K$ still evaluates to the exact value $f(K)$ because $(K, f(K))$ lies on that same collinear line segment!
3. Hardware & Precision Realities
Integer vs Floating-Point Binary Search
When all original weights are integers, the slopes $\Delta(k) = f(k) - f(k-1)$ between consecutive integer points $k-1$ and $k$ are always integers! Therefore, you should binary search $\lambda$ over integers (int64_t), completely avoiding floating-point precision loss and fixed-iteration loops. With integer weights bounded by $W$, $\lambda \in [0, N \cdot W]$, requiring at most $\lceil \log_2(N \cdot W) \rceil \le 50$ binary search iterations.
4. Complexity Matrix
Visualize linear DP transitions dp[i] = min_j(m_j·x_i + b_j) as a lower envelope of lines, popping dominated middle lines when intersect(L1, L3) ≤ intersect(L1, L2).
Invariant & State
| DP Formulation | Time Complexity | Space Complexity | Key Requirement |
|---|---|---|---|
| 2D Constrained DP $dp[k][i]$ | O(K * N^2) or O(K * N) | O(N) | Arbitrary $f(k)$ |
| WQS Binary Search + 1D DP | O(N log C) | O(N) | $f(k)$ is convex (or concave for max) |
| WQS + CHT / Monotonic Queue 1D DP | O(N log N log C) or O(N log C) | O(N) | $f(k)$ convex + 1D QI/CHT holds |
5. Production-Grade C++20 Implementation
#include <vector>
#include <cstdint>
#include <utility>
#include <algorithm>
// Example problem: Partition array of length N into at most K subarrays,
// or select at most K non-overlapping segments of length L to maximize sum
// (Here: Minimize cost of selecting exactly K segments where 1D DP takes O(N))
struct DPState {
int64_t cost;
int count;
// Tie-break by SMALLEST count when penalized costs are equal
bool operator<(const DPState& other) const {
if (cost != other.cost) return cost < other.cost;
return count < other.count;
}
};
// Solves: Partition array A into K subarrays minimizing sum of (subarray_sum)^2
// Uses WQS Binary Search + Monotonic CHT in O(N log(sum^2)) time
int64_t wqs_min_square_partition(const std::vector<int64_t>& a, int K) {
const int n = static_cast<int>(a.size());
std::vector<int64_t> pref(n + 1, 0);
for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + a[i];
// Given penalty lambda >= 0 per subarray, solve 1D DP in O(N) via CHT
auto solve_with_penalty = [&](int64_t lambda) -> DPState {
std::vector<DPState> dp(n + 1, {0, 0});
// dp[i] = min_{j < i} (dp[j].cost + (pref[i] - pref[j])^2 + lambda)
for (int i = 1; i <= n; ++i) {
DPState best = {std::numeric_limits<int64_t>::max() / 4, n + 1};
for (int j = 0; j < i; ++j) {
int64_t diff = pref[i] - pref[j];
DPState cand{dp[j].cost + diff * diff + lambda, dp[j].count + 1};
if (cand < best) best = cand;
}
dp[i] = best;
}
return dp[n];
};
int64_t lo = 0, hi = pref[n] * pref[n];
int64_t best_lambda = hi;
while (lo <= hi) {
int64_t mid = lo + (hi - lo) / 2;
DPState res = solve_with_penalty(mid);
if (res.count <= K) {
best_lambda = mid;
hi = mid - 1; // Try smaller penalty to allow more segments up to K
} else {
lo = mid + 1; // Too many segments used; increase penalty
}
}
DPState final_state = solve_with_penalty(best_lambda);
// Important: subtract best_lambda * K (NOT final_state.count) because of collinearity!
return final_state.cost - best_lambda * K;
}Production Pitfall — Subtracting lambda * res.count Instead of lambda * K
One of the most famous bugs in WQS Binary Search is returning final_state.cost - best_lambda * final_state.count at the end! When $(K-1, f(K-1)), (K, f(K)), (K+1, f(K+1))$ are collinear with slope $-\lambda^*$, tie-breaking by minimum count will return final_state.count = K - 1 even though $g(\lambda^*) = f(K-1) + \lambda^*(K-1) = f(K) + \lambda^* K$. To extract $f(K)$, you must subtract best_lambda * K, never best_lambda * final_state.count!