Hi everyone!
Previously, I wrote a general introduction to linear programming duality. In this blog, I would like to write about several problems that could be solved with this technique. Familiarity with the first blog, or general knowledge of dual problems and how to construct them is generally expected to navigate in this one.
Thanks to brunovsky and Golovanov399 for problem suggestions!
And particularly special thanks to WeakestTopology for problem suggestions and all insightful discussions on the topic!
Dual construction mnemonics
To simplify the construction of dual problems, let's recall the correspondence between constraints/variables in primal and dual problems.
LP duality mnemonicsStandard definition of LP dual problem looks like this:
$$$\begin{gather} \max\limits_x & c^\top x & \color{red}{\text{(maximization)}} & \overset{\text{dual}}{\iff} & \min\limits_\lambda & b^\top \lambda & \color{red}{\text{(minimization)}} \\ s.t. & Ax \leq b & \color{red}{\text{(constraint }\leq\text{)}} & & s. t. & \lambda \geq 0 & \color{red}{\text{(variable }\geq\text{)}} \\ & x \geq 0 & \color{red}{\text{(variable }\geq\text{)}} & & & A^\top \lambda \geq c & \color{red}{\text{(constraint} \geq \text{)}} \end{gather}$$$Considering some more generic forms, it may be summarized in a table:
Maximization | Minimization |
Inequality constraint $$$\leq$$$ | Nonnegative variable $$$\geq$$$ |
Inequality constraint $$$\geq$$$ | Nonpositive variable $$$\leq$$$ |
Equality constraint $$$=$$$ | Free variable |
Nonnegative variable $$$\geq$$$ | Inequality constraint $$$\geq$$$ |
Nonpositive variable $$$\leq$$$ | Inequality constraint $$$\leq$$$ |
Free variable | Equality constraint $$$=$$$ |
Or, keeping it more visual, we may write it as follows:
$$$\begin{gather} \max\limits_{x,y,z} & c^\top x + d^\top y + f^\top z & \overset{\text{dual}}{\iff} & \min\limits_{\lambda,\eta,\mu} & p^\top \lambda + q^\top \eta + r^\top \mu \\ s.t. & Ax+By+Cz \leq p & & s.t. & \lambda \geq 0 \\ & Dx + Ey + Fz \geq q & & & \eta \leq 0 \\ & Gx + Hy + Jz = r & & & \mu\text{ free} \\ & x \geq 0 & & & A^\top \lambda + D^\top \eta + G^\top \mu \geq c \\ & y \leq 0 & & & B^\top \lambda + E^\top \eta + H^\top \mu \leq d \\ & z\text{ free} & & & C^\top \lambda + F^\top \eta + J^\top \mu = f \end{gather}$$$ Swapping variables and constraints
Let's continue from where we left in the previous article:
605C - Мечты фрилансера. There are $$$n$$$ jobs. The $$$i$$$-th job gets you $$$a_i$$$ experience and $$$b_i$$$ dollars per second. You want to gain at least $$$p$$$ experience and at least $$$q$$$ money overall, while spending as little time overall as possible. How much time would it take?
Primal formulationStatement as it is boils down to the following LP problem, given $$$a_1, \dots, a_n, b_1, \dots, b_n, p, q$$$:
$$$\boxed{\begin{gather} \min\limits_{t_k \in \mathbb R} & t_1 + \dots + t_n, \\ s.t. & t_1 a_1 + \dots + t_n a_n \geq p, \\ & t_1 b_1 + \dots + t_n b_n \geq q, \\ & t_i \geq 0. \end{gather}}$$$ Dual formulationIts dual is
$$$\boxed{\begin{gather} \max\limits_{\lambda,\mu \in \mathbb R} & \lambda p + \mu q, \\ s.t. &\lambda a_i + \mu b_i \leq 1, &(\forall i) \\ &\lambda, \mu \geq 0. \end{gather}}$$$ SolutionThe optimal solution to the dual problem can be found in $$$O(\log C)$$$ with ternary search.
So, the first nice property of LP duality in competitive programming is that it allows to swap variables and constraints, effectively reducing the dimensions of the problem when there are very little constraints.
Dual of minimum cost flow
Library Checker — Minimum cost b-flow. Given a flow network, find a minimum cost $$$\mathbf b$$$-flow $$$\mathbf f$$$ and its dual $$$\mathbf \pi$$$.
Primal formulationMinimum cost $$$b$$$-flow is formulated as LP problem in the following way:
$$$\boxed{\begin{gather} \min\limits_{f_{ij} \in \mathbb R} & \sum\limits_{i,j} f_{ij} c_{ij}, \\ s.t. & 0 \leq f_{ij} \leq q_{ij}, &(\forall i,j) \\ & \sum\limits_{j=1}^n f_{kj} - \sum\limits_{i=1}^n f_{ik} = b_k, &(\forall k) \\ & b_s = b, b_t = -b, \\ & b_k = 0. & (\forall k \not \in \{s, t\}) \end{gather}}$$$Note that Library Checker's formulation is a bit more generic and also uses lower constraints $$$l_{ij} \leq f_{ij}$$$ instead of just $$$0 \leq f_{ij}$$$, besides $$$b_1, \dots, b_n$$$ in Library Checker's formulation are given in input, rather than fixed with source $$$s$$$ and sink $$$t$$$. Worst of all, it seemingly allows negative cost cycles, thus one would need to utilize some algorithm that finds a minimum cost circulation after finding some $$$b$$$-flow.
We will only consider simplified version above to share the core idea.
In terms of the primary problem, the dual variables are defined by the complementary slackness:
- If $$$f_{ij} > 0$$$, then $$$c_{ij}^\pi \leq 0$$$;
- If $$$f_{ij} < q_{ij}$$$, then $$$c_{ij}^\pi \geq 0$$$.
Here $$$c_{ij}^\pi = c_{ij} + \pi_j - \pi_i$$$ is the adjusted cost of the edge $$$i \to j$$$.
For further detailed explanation, please refer to the minimum cost flow part of my previous article.
Dual formulationThe dual of minimum cost $$$b$$$-flow problem may be formulated directly as
$$$\boxed{\begin{gather} \max\limits_{\pi_k \in \mathbb R} & \sum\limits_{i,j} \min(0, c_{ij} - \pi_i + \pi_j) q_{ij} - b(\pi_t - \pi_s) \end{gather}}$$$ SolutionOne of possible way to find $$$\pi_k$$$ knowing the residual network of a minimum cost $$$b$$$-flow is to assign $$$\pi_k$$$ the negated shortest path length from $$$s$$$ to $$$k$$$ in the residual network. Alternatively, $$$\pi_k$$$ may be perceived as the shortest path from $$$k$$$ to $$$t$$$. Knowing residual network of a minimum cost $$$b$$$-flow, it's possible to compute potentials in $$$O(nm)$$$ with any shortest path algorithm that allows negative edges.
Again, for further detailed explanation, please refer to the minimum cost flow part of my previous article.
In this way, dual solution may be found even if you didn't use Dijkstra with potentials and e.g. used SPFA instead.
Inverse MST
acmsguru — 206. Roads. Given a weighted graph and its spanning tree $$$T$$$, you need to adjust weights of graph edges from $$$c_i$$$ to $$$d_i$$$ in such way that the sum of $$$|c_i - d_i|$$$ is minimum possible and $$$T$$$ is a minimum spanning tree of the graph with new edges.
Primal formulationGenerally, it is a known property that a spanning tree is minimum if and only if the cost of any external edge $$$j$$$ is not smaller than any cost of an edge on the tree path $$$p_j$$$ that connects the endpoints of $$$j$$$. In other words, $$$d_i \leq d_j (\forall i \in p_j)$$$.
The statement above, using $$$d_i = c_i - x_i$$$ for $$$i \in T$$$ and $$$d_j = c_j + x_j$$$ for $$$j \not \in T$$$, is formulated as an LP problem in the following way:
$$$\boxed{\begin{gather} \min\limits_{x_k \in \mathbb R} & x_1 + \dots + x_m \\ s.t.& c_i - x_i \leq c_j + x_j, & (\forall j \not \in T, \forall i \in p_j) \\ & x_i \geq 0. & (\forall i) \end{gather}}$$$ Dual formulationSolving the original problem is not a trivial task, however we might formulate its dual:
$$$\boxed{\begin{gather} \max\limits_{\lambda_{ij} \in \mathbb R} & \sum\limits_j \sum\limits_{i \in p_j} \lambda_{ji} (c_i - c_j) \\ s.t.& \sum\limits_{i \in p_j} \lambda_{ji} \leq 1, & (\forall j \not \in T) \\ & \sum\limits_{j : i \in p_j} \lambda_{ji} \leq 1, & (\forall i \in T) \\ & \lambda_{ji} \geq 0. & (\forall j \not \in T, \forall i \in p_j) \end{gather}}$$$ SolutionIt's not hard to see that the dual is, in fact, an assignment problem on bipartite graph.
Edges $$$i \in T$$$ form one part of the graph, while edges $$$j \not\in T$$$ form another part of the graph, and the edge between $$$i$$$ and $$$j$$$ costs $$$c_{i} - c_j$$$ and has the capacity $$$1$$$. This already allows us to recover the minimum sum $$$x_1 + \dots + x_m$$$, but the problem asks us to find optimal $$$d_1, \dots, d_m$$$, that is to also find the actual values of $$$x_1,\dots, x_m$$$.
For convenience, let's change edge weights from $$$c_i - c_j$$$ to $$$c_j - c_i$$$ and work with minimum cost flow instead, as we're more familiar with its potentials and their properties than with maximum cost flow.
Let's see how minimum cost flow potentials relate with this problem. Adjusted weights of edges in minimum cost flow are defined as $$$c_{ij}^\pi = c_{ij} + \pi_j - \pi_i$$$. And we know that $$$c_{ij}^\pi \geq 0$$$ for non-saturated edges, while $$$c_{ij}^\pi \leq 0$$$ for edges with non-zero flow. What does it mean for edges in the residual network? The edge $$$i \to j$$$ of cost $$$c_j - c_i$$$ would change to
$$$ c_j - c_i + \pi_j - \pi_i = (c_j + \pi_j) - (c_i + \pi_i). $$$Then, making edge $$$i \to j$$$ of infinite capacity, we will guarantee that $$$c_{ij}^\pi = 0$$$ for edges that participate in the assignment and $$$c_{ij}^\pi \geq 0$$$ for all other edges, hence $$$c_j + \pi_j \geq c_i + \pi_i$$$ for any edge in the bipartite graph. This means that
$$$ x_k = \begin{cases} -\pi_k, & k < n, \\ \pi_k, & k \geq n \end{cases} $$$would define feasible values of $$$x_1, \dots, x_m$$$. Not necessarily optimal however. What is the total cost of the assignment defined by the residual network with potentials $$$\pi_1, \dots, \pi_m$$$? Any edge participating in the assignment would have zero cost and won't contribute to the assignment value. This only leaves us with edges $$$s \to i$$$, having costs $$$\pi_i-\pi_s$$$ and edges $$$j \to t$$$, having cost $$$\pi_t-\pi_j$$$. Here, $$$\pi_t$$$ and $$$\pi_s$$$ summed up together give an extra factor of $$$b(\pi_t - \pi_s)$$$ in the minimum cost dual.
In this factor we should note that $$$\pi_s=0$$$ by definition when using shortest path from $$$s$$$ potentials, and $$$\pi_t \geq 0$$$ in the moment at which we're no longer able to use augmenting paths of negative cost. To not consider $$$\pi_t > 0$$$ case separately it is convenient to adjust the flow network by adding a direct edge $$$s \to t$$$ of cost $$$0$$$ and positive capacity. This way we guarantee that when all negative-cost paths are exhausted, we will have $$$\pi_t=0$$$ and thus we may ignore it.
The property above means that the optimal cost is obtained if we only use potentials of the vertices that actually participate in the assignment. It hints that we may just change potentials of all the other vertices to $$$0$$$ and it would still be a feasible solution.
Why is it true? Consider a vertex $$$i$$$ in the first part of the bipartite graph that wasn't taken in the assignment. Its potential (negated shortest path from $$$s$$$) must be non-negative, as there is still an edge $$$s \to i$$$ of the cost $$$0$$$. Consider a vertex $$$j$$$ in the second part that wasn't taken in the assignment. Its potential must be non-positive, as there is still an edge $$$j \to t$$$.
If we'd use such potentials in $$$x_i$$$ and $$$x_j$$$ we would increase the cost of edges in $$$T$$$ and decrease the cost of edges not in $$$T$$$. We get a feasible solution after doing it, but it means that we were fine before doing it to begin with, so changing the potentials to $$$0$$$ is OK.
Summarizing everything above, the algorithm is as follows:
- Construct the flow network for the assignment problem;
- Add an extra edge $$$s \to t$$$ with cost $$$0$$$ and positive capacity;
- Find minimum-cost flow $$$f$$$;
- Find the potentials, $$$\pi_k$$$ for vertex $$$k$$$ is the negated length of a shortest path from $$$s$$$ to $$$k$$$ in the residual network;
- For every $$$k$$$ that participates in the resulting assignment (is incident to saturated edge), add $$$\pi_k$$$ to $$$c_k$$$ to get $$$d_k$$$.
Possible implementation.
Duality... On segments?
1696G - Fishingprince снова играет с массивом. You may do the following operations with the array $$$a_1, \dots, a_n$$$:
- Pick $$$1 \leq i < n$$$, then decrease $$$a_i$$$ by $$$x$$$ per second and decrease $$$b_i$$$ by $$$y$$$ per second;
- Pick $$$1 \leq i < n$$$, then decrease $$$a_i$$$ by $$$y$$$ per second and decrease $$$b_i$$$ by $$$x$$$ per second.
Let $$$f(a_1, \dots, a_n)$$$ be the minimum time needed to make all $$$a_k$$$ less or equal than zero. Process $$$q$$$ queries of the following kind:
- Change $$$a_k$$$ to $$$v$$$;
- Given $$$l$$$ and $$$r$$$, print $$$f(a_l, \dots, a_r)$$$.
In this problem, it always holds that $$$a_k \geq 1$$$ for all $$$k$$$.
Primal formulationThe problem is quite similar to 605C that is explained above. It's LP formulation is as follows:
$$$\boxed{\begin{gather} \min\limits_{p_i, q_j \in \mathbb R} & (p_1 + \dots + p_{n-1})+(q_1 + \dots + q_{n-1}) \\ s.t. & x(p_i + q_{i-1}) + y(q_i + p_{i-1}) \geq a_i, & (\forall i > 1) \\ & x p_1 + y q_1 \geq a_1, & \\ & p_i, q_j \geq 0. & (\forall i, j) \end{gather}}$$$ Dual formulationFor each of $$$n$$$ constraints, we'll have a dual variable $$$\pi_k$$$ and each of $$$2n-2$$$ primal variables will generate a constraint.
To get the coefficient near $$$i$$$-th dual variable in the $$$j$$$-th constraint, we take the coefficient near $$$j$$$-th primal variable in the $$$i$$$-th primal constraint. E.g. the variable $$$p_k$$$ occurs in the $$$k$$$-th constraint with the coefficient $$$x$$$ and in the $$$(k+1)$$$-th constraint with the coefficient $$$y$$$:
$$$\boxed{\begin{gather} \max\limits_{\pi_k \in \mathbb R} & \pi_1 a_1 + \dots + \pi_n a_n, \\ s.t. & x \pi_k + y \pi_{k+1} \leq 1, & (\forall k < n) \\ & y \pi_k + x \pi_{k+1} \leq 1, & (\forall k < n) \\ & \pi_k \geq 0. & (\forall k) \end{gather}}$$$ SolutionConsider the case of only two variables:
$$$\begin{gather} \max\limits_{\pi_1,\pi_2 \in \mathbb R} & \pi_1 a_1 + \pi_2 a_2, \\ s.t. & x \pi_1 + y \pi_{2} \leq 1, \\ & y \pi_1 + x \pi_{2} \leq 1, \\ & \pi_1,\pi_2 \geq 0. \end{gather}$$$The constraints define a quadrilateral with four vertices:
The quadrilateral defined by the inequalities and its vertices Thus the space of allowed $$$\pi_1, \dots, \pi_n$$$ may be interpreted in the following way: There is a convex quadrilateral defined by the inequalities and $$$(n-1)$$$ points, $$$k$$$-th point having coordinate $$$(\pi_k, \pi_{k+1})$$$. You may arbitrary number of times add same value to the $$$x$$$ coordinate of the $$$k$$$-th point and $$$y$$$ coordinate of the $$$(k-1)$$$-th point, while making sure that all points stay within the quadrilateral.
Besides that, you may freely change the $$$x$$$ coordinate of the first point and the $$$y$$$ coordinate of the last point, obviously always making them as large as possible, as $$$a_1,\dots, a_n \geq 0$$$.
Next step in the solution is to notice that it's always possible to pick a solution of LP which is a vertex of the polytope defined by the constraints (as long as the polytope is bounded). That is, it's always possible to pick a subset of $$$n$$$ inequalities that will be "saturated". In this particular problem, however, all inequalities concern either only $$$1$$$ or only $$$2$$$ variables, so we may construct a graph in which there is an edge between $$$i$$$ and $$$j$$$ whenever there is an inequality that concerns both $$$\pi_i$$$ and $$$\pi_j$$$.
In such graph, an edge $$$(u, v)$$$ would mean that we're able to recover $$$u$$$ if we know $$$v$$$ and vice versa. Besides that, it is also possible to resolve any cycle, as substituting variables along the cycle allows us to return to the first variable of the cycle with the equation of form $$$ax=b$$$. For the set of $$$n$$$ equations to have a unique solution it is sufficient that each connected component has a cycle. Moreover, since we only use $$$n$$$ edges for $$$n$$$ vertices, the cycle of each component must be unique.
Another particularity of this specific problem is that all cycles, if they're unique in their connected component, will be either self-loops (if we take the equation $$$\pi_k = 0$$$) or between only two vertices (if we take both equations $$$x\pi_k + y \pi_{k+1} = 1$$$ and $$$x \pi_{k+1} + y \pi_k = 1$$$).
In the first case, vertices with even distance from the root will hold $$$0$$$.
And the vertices with odd distance from the root will hold $$$\frac{1}{\max(x, y)}$$$, because $$$\frac{1}{\min(x, y)}$$$ would violate the constraints.
In the second case, all vertices in the connected component will hold the value of $$$\frac{1}{x+y}$$$.
Duality in bipartite graphs
ARC 125 — Snack. There are $$$m$$$ kids and $$$n$$$ kinds of snacks. Distribute maximum amount of snack among children in such way that
- Total distributed amount of $$$j$$$-th snack is at most $$$A_j$$$;
- Total amount of each snack type distributed to $$$i$$$-th child is at most $$$B_i$$$;
- Total amount of snacks distributed to $$$i$$$-th child is at most $$$C_i$$$.
Primal formulationPrimal problem is formulated in a straightforward manner. Let $$$x_{ij}$$$ be the amount of snack of type $$$j$$$ distributed to $$$i$$$-th child:
$$$\boxed{\begin{gather} \max\limits_{x_{ij} \in \mathbb R} & \sum\limits_{i,j} x_{ij}, \\ s.t. & \sum\limits_i x_{ij} \leq A_j, & (\forall j) \\ & \sum\limits_j x_{ij} \leq C_i, & (\forall i) \\ & 0 \leq x_{ij} \leq B_i. & (\forall i, j) \end{gather}}$$$It can as well be perceived as a maximum flow problem, such that from the source $$$s$$$ to $$$j$$$-th snack there is an edge of capacity $$$A_j$$$, from $$$j$$$-th snack to $$$i$$$-th child there is an edge of capacity $$$B_i$$$ and from $$$i$$$-th child to the sink $$$t$$$ there is an edge of capacity $$$C_i$$$.
Dual formulationThe network is too huge for computing maximum flow on it, so let's write the dual problem. There will be $$$n+m+nm$$$ dual variables, let $$$\lambda_j$$$ be a variable for the $$$\leq A_j$$$ constraint, $$$\mu_i$$$ be a variable for the $$$\leq C_i$$$ constraint and $$$\nu_{ij}$$$ be a variable for the $$$\leq B_i$$$ constraint.
Then, the dual problem is written as
$$$\boxed{\begin{gather} \min\limits_{\lambda_j, \mu_i, \nu_{ij} \in \mathbb R} & \sum\limits_j A_j \lambda_j + \sum\limits_i C_i \mu_i + \sum\limits_{i,j} B_i \nu_{ij}, \\ s.t. & \lambda_j + \mu_i + \nu_{ij} \geq 1, & (\forall i, j) \\ & \lambda_j, \mu_i, \nu_{ij} \geq 0. & (\forall i, j) \end{gather}}$$$ SolutionSince the primal problem is a maximum flow in the bipartite graph, its dual may be interpreted as minimum cut in the graph. To be more specific, each of the variables $$$\lambda_j$$$, $$$\mu_i$$$ and $$$\nu_{ij}$$$ will be either $$$0$$$ or $$$1$$$, depending on whether corresponding edges are taken into the cut.
It means that for each pair $$$(j, i)$$$, we either we delete the $$$j$$$-th vertex in the first part ($$$\lambda_j = 1$$$) and pay $$$A_j$$$, or delete the $$$i$$$-th vertex in the second part ($$$\mu_i = 1$$$) and pay $$$C_i$$$ or delete the edge from $$$j$$$-th vertex in the first part to the $$$i$$$-th vertex in the second part and pay $$$B_i$$$.
Let $$$X_0$$$ and $$$Y_0$$$ be the sets of removed vertices in the first and the second parts correspondingly, and let $$$X_1$$$ and $$$Y_1$$$ be the sets of non-removed vertices in the parts. Then the value of the target function is expressed as
$$$ \sum\limits_{j \in X_0} A_j + \sum\limits_{i \in Y_0} C_i + \sum\limits_{\substack{j \in X_1 \\ i \in Y_1}} B_i. $$$Using the fact that the third sum does not depend on $$$A_1$$$, but only on its size, we further rewrite it as
$$$ \sum\limits_{j \in X_0} A_j + \sum\limits_{i \in Y_0} C_i + |X_1|\sum\limits_{\substack{i \in Y_1}} B_i. $$$Let $$$f(k)$$$ be the minimum value of the target function with $$$|X_1| = k$$$, then
$$$ f(k) = \min\limits_{|X_0| = n - k} \sum\limits_{j \in X_0} A_j + \sum\limits_{i} \min(C_i, k B_i). $$$For each specific $$$k$$$, it is always optimal to pick $$$X_0$$$ as a prefix of all snacks, sorted in increasing order of $$$A_j$$$. At the same time, for each $$$i$$$ we know the minimum $$$k$$$ starting from which it is better to use $$$C_i$$$ rather than $$$k B_i$$$. Together, it allows to compute $$$f(k)$$$ for any fixed $$$k$$$ in $$$O(\log n)$$$ amortized time by e.g. using prefix sums and binary search. Then, you just pick $$$k$$$ such that $$$f(k)$$$ is minimum possible.
The problem could as well be solved with minimum cut directly, but perhaps duality makes it more evident.
Besides, it sheds some light on how flow LP looks like in bipartite graphs, which is particularly useful in the following task.
Duality in bipartite graphs 2
ABC 224 — Security Camera 2. You have a bipartite graph $$$(L, R)$$$. You may pay $$$A_i$$$ to put $$$1$$$ camera at vertex $$$i \in L$$$ or pay $$$B_j$$$ to put $$$1$$$ camera at vertex $$$j \in R$$$. For every pair $$$(i, j)$$$ you want the total number of cameras installed in $$$i \in L$$$ and $$$j \in R$$$ to be at least $$$C_{ij}$$$. What is the least amount you need to pay to satisfy this condition?
Primal formulationLet $$$\alpha_i$$$ be the number of cameras in $$$i \in L$$$ and $$$\beta_j$$$ be the number of cameras in $$$j \in R$$$. Then the primal LP is as follows:
$$$\boxed{\begin{gather} \min\limits_{\alpha_i, \beta_j \in \mathbb R} & \sum\limits_{i \in L} A_i \alpha_i + \sum\limits_{j \in R} B_i \beta_j, \\ s.t. & \alpha_i + \beta_j \geq C_{ij} & (\forall i, j) \\ & \alpha_i, \beta_j \geq 0. & (\forall i, j) \end{gather}}$$$ Dual formulationDual problem will introduce a dual variable $$$\lambda_{ij}$$$ for each constraint. Then it is formulated as
$$$\boxed{\begin{gather} \max\limits_{\lambda_{ij} \in \mathbb R} & \sum\limits_{i,j} C_{ij} \lambda_{ij}, \\ s.t. & \sum\limits_{j \in R} \lambda_{ij} \leq A_i, & (\forall i) \\ & \sum\limits_{i \in L} \lambda_{ij} \leq B_j, & (\forall j) \\ & \lambda_{ij} \geq 0. & (\forall i, j) \end{gather}}$$$ SolutionFormulation is quite similar to ARC 125 Snack. Indeed, it's nothing but the maximum cost flow in the network constructed as follows:
- There is an edge of cost $$$0$$$ and capacity $$$A_i$$$ from $$$s$$$ to every $$$i \in L$$$;
- There is an edge of cost $$$0$$$ and capacity $$$B_j$$$ from every $$$j \in R$$$ to $$$t$$$;
- There is an edge of cost $$$C_{ij}$$$ and capacity $$$+\infty$$$ from $$$A_i$$$ to $$$B_j$$$ for every $$$i \in L$$$ and $$$j \in R$$$.
Bonus: How to recover the answer (amount of cameras in each vertex)?
Is this aliens trick?
XIX Open Cup, Grand Prix of Korea — Utilitarianism. Given a weighted tree, find a maximum-weight matching of exactly $$$k$$$ edges.
Primal formulationNote that any tree is a bipartite graph, and maximum-cost $$$k$$$-matching can be formulated as follows:
$$$\boxed{\begin{gather} \max\limits_{x_{ij} \in \mathbb R} & \sum\limits_{(i, j) \in E} C_{ij} x_{ij}, \\ s.t. & \sum\limits_{j : \{i, j\} \in E} x_{ij} \leq 1, & (\forall i \in V) \\ & \sum\limits_{\{i, j\} \in E} x_{ij} = k,\\ & x_{ij} \geq 0. & (\forall i, j) \end{gather}}$$$ Dual formulationLet $$$\nu_i$$$ be a dual variable for $$$i \in V$$$ constraint, and $$$\lambda$$$ be a dual variable for $$$=k$$$ constraint. The dual problem is formulated as
$$$\boxed{\begin{gather} \min\limits_{\nu_i, \lambda \in \mathbb R} & \sum\limits_{i \in V} \nu_i + \lambda k, \\ s.t. & \nu_i + \nu_j + \lambda \geq C_{ij}, & (\forall \{i, j\} \in E) \\ & \nu_i \geq 0. & (\forall i) \end{gather}}$$$ SolutionLet $$$t(\lambda)$$$ be the minimum with a fixed $$$\lambda$$$. Then the value $$$t(\lambda) - \lambda k$$$ is the solution to the minimization problem
$$$\begin{gather} \min\limits_{\nu_i, \lambda \in \mathbb R} & \sum\limits_{i \in V} \nu_i, \\ s.t. & \nu_i + \nu_j \geq C_{ij}^\lambda, & (\forall \{i, j\} \in E) \\ & \nu_i \geq 0. & (\forall i) \end{gather}$$$Here $$$C_{ij}^\lambda = C_{ij} - \lambda$$$. If we're able to compute $$$t(\lambda)-\lambda k$$$ for any $$$\lambda$$$, we may note that the function is convex and therefore its minimum can be found by ternary search. But how to compute it for a fixed $$$\lambda$$$?
There are two ways here. First of all, you can take the second dual and obtain
$$$\begin{gather} \max\limits_{x_{ij} \in \mathbb R} & \sum\limits_{(i, j) \in E} C_{ij}^\lambda x_{ij}, \\ s.t. & \sum\limits_{j : \{i, j\} \in E} x_{ij} \leq 1, & (\forall i \in V) \\ & x_{ij} \geq 0. & (\forall i, j) \end{gather}$$$This is essentially the same problem as the initial one, but this time without $$$=k$$$ constraint. It can be solved in $$$O(n)$$$ with DP on tree.
The other option is to solve for $$$t(\lambda) - \lambda k$$$ directly. This option is left to the curious reader as an exercise.
Yes, this is essentially the aliens trick. Note that aliens trick is a bit more general than LP duality, and may work for non-linear problems. However, LP problems is quite large class of cases for which aliens trick will consistently work, without need to prove it every time.
Bonus: Solve the dual problem directly, without taking a second dual of it.
Duality... On subsets?!
1430G - Очередное взвешивание графа. You're given a weighted DAG on $$$n \leq 18$$$ vertices. You need to assign each vertex an integer $$$a_i$$$, so that for each edge $$$i \to j$$$ the value of $$$a_i - a_j > 0$$$ and the total sum of $$$w_{ij} (a_i - a_j)$$$ is minimized.
Primal formulationThe problem is formulated as follows:
$$$\boxed{\begin{gather} \min\limits_{a_i \in \mathbb R} & \sum\limits_{(i, j) \in E} w_{ij} (a_i - a_j), \\ s.t. & a_i - a_j \geq 1. & (\forall (i, j) \in E) \end{gather}}$$$Here we used $$$\geq 1$$$ constraint as this is the minimum possible difference between two integers.
Dual formulationWe will have a dual variable $$$\lambda_{ij}$$$ for each edge $$$(i,j) \in E$$$:
$$$\boxed{\begin{gather} \max\limits_{\lambda_{ij} \in \mathbb R} & \sum\limits_{(i, j) \in E} \lambda_{ij}, \\ s.t. & \sum\limits_{(i,j) \in E} \lambda_{ij} - \sum\limits_{(j,i) \in E}\lambda_{ji} = b_i, & (\forall i \in V) \\ &\lambda_{ij} \geq 0. & (\forall i, j) \end{gather}}$$$Here $$$b_i$$$ is the "balance" of each vertex, defined as
$$$ b_i = \sum\limits_{(i,j) \in E} w_{ij} - \sum\limits_{(j,i) \in E}w_{ji}. $$$ SolutionEssentially the dual problem tells us that the $$$i$$$-th vertex should create (if $$$b_i > 0$$$) or absorb (if $$$b_i < 0$$$) the amount of flow that is equal to $$$|b_i|$$$. At the same time each edge has a cost $$$1$$$ and capacity $$$+\infty$$$, and we want to compute a flow of maximum cost.
To reduce flow creation and absorbtion to only two vertices, we will say that when $$$b_i > 0$$$, there is an edge of cost $$$0$$$ and capacity $$$b_i$$$ from $$$s$$$ to $$$i$$$. Otherwise, we make an edge from $$$i$$$ to $$$t$$$ of cost $$$0$$$ and capacity $$$-b_i$$$.
Note that we need to not only find the size of the answer, but also to recover it. As with inverse MST, we will once again use Johnson's potentials and the complementary slackness.
Let $$$c_{ij}^\pi = c_{ij}+\pi_j - \pi_i$$$ be the adjusted cost of the edge. As we remember, for non-saturated edges it holds that $$$c_{ij}^\pi \geq 0$$$ and for edges with non-zero flow it holds that $$$c_{ij}^\pi \leq 0$$$.
At the same time, for the edges of the initial graph that are used in the flow, it is guaranteed that $$$c_{ij}^\pi = 0$$$, as their capacity is infinite, so they can't be saturated. In other words, for any edge $$$i \to j$$$ it holds that $$$c_{ij} + \pi_j - \pi_i = c_{ij}^\pi \leq 0$$$. Using $$$c_{ij}=1$$$ it means that $$$\pi_i - \pi_j \geq 1$$$ for any edge $$$i \to j$$$, which is exactly what the statement asks for.
On the other hand, the total cost of the flow is determined solely by the edges from $$$s$$$ to $$$i$$$, which contribute $$$b_i\pi_i$$$ to the cost of the flow and the edges from $$$j$$$ to $$$t$$$, which contribute $$$b_j(\pi_t-\pi_j)$$$. Summed up altogether this is equal to the sum of $$$w_{ij} (\pi_i - \pi_j)$$$, as the primal problem asks for, plus an excess of $$$b \pi_t$$$. But this excess is exactly the difference between the mincost flow on the initial and adjusted edges, as this difference is generally equal to $$$b(\pi_t - \pi_s)$$$ and $$$\pi_s=0$$$ from they way we compute potentials.
That being said, the solution is $$$a_k = \pi_k$$$, where $$$\pi_k$$$ is the negated length of the shortest path from $$$s$$$ to $$$k$$$ in the residual network of the maximum flow of maximum cost. Possible implementation.
Nope, no subsets or bitmasks here. The intended solution uses them, hence $$$n \leq 18$$$, but the solution with LP duality is polynomial, so it provides a significant improvement in the complexity of the algorithm.
Inefficient slope trick
713C - Соня и задача без легенды. You're given the array $$$a_1, \dots, a_n$$$. You may increase or decrease some elements of the array arbitrary number of times. What is the smallest number of changes you need to do to make the array non-decreasing?
The problem is famous for being exemplar problem for "slope trick", still it can also be solved less efficiently with duality.
Primal formulationLet's say that we add $$$\alpha_i$$$ and subtract $$$\beta_i$$$ from $$$a_i$$$. Then it's formulated as
$$$\boxed{\begin{gather} \min\limits_{\alpha_i, \beta_i \in \mathbb R} & \sum\limits_i (\alpha_i + \beta_i), \\ s.t. & a_i + \alpha_i - \beta_i \leq a_{i+1} + \alpha_{i+1}-\beta_{i+1}, & (\forall i < n), \\ & \alpha_i, \beta_i \geq 0. & (\forall i) \end{gather}}$$$ Dual formulationIn the dual formulation, we will have $$$n-1$$$ dual variables $$$\lambda_1, \dots, \lambda_{n-1}$$$, so the dual is formulated as
$$$\boxed{\begin{gather} \max\limits_{\lambda_i \in \mathbb R} & \sum\limits_i \lambda_i(a_i - a_{i+1}), \\ s.t. & |\lambda_i - \lambda_{i-1}| \leq 1, & (\forall i > 1), \\ & \lambda_1 \leq 1, \\ & \lambda_i \geq 0. & (\forall i) \end{gather}}$$$ SolutionIn other words, you start with $$$\lambda_1=0$$$ or $$$\lambda_1=1$$$, then each consequent variable is either the same as the previous one, or deviates from it by $$$1$$$. Besides that, $$$\lambda_i$$$ is not allowed to go negative. You need to pick them in a way that maximizes scalar product of $$$\lambda$$$ with partial difference array $$$a_{i} - a_{i+1}$$$. This can be done in $$$O(n^2)$$$ with dynamic programming of kind $$$dp[i][j]$$$ being the maximum possible prefix sum of such products up to $$$i$$$, while using $$$\lambda_i=j$$$.
Bonus: Can you solve the dual problem, i.e. find $$$\lambda_1, \dots, \lambda_n$$$, faster than $$$O(n^2)$$$?
Further exercises
I heard that the following problems can also be solved by LP duality, so you may practice on them if you want more.
Wow, this is super interesting!