Hi everyone!
Previously, I wrote a general introduction about 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.
Swapping variables and constraints
Let's continue from where we left in the previous article:
605C - Freelancer's Dreams. 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?
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$$$.
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.
Duality... On segments?
1696G - Fishingprince Plays With Array Again. 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$$$.
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$$$.
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?
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.
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 - Yet Another DAG Problem. 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.
Nope, no subsets or bitmasks here. The intended solution uses them, hence $$$n \leq 18$$$, but the solution with LP duality is polynomial.
Inefficient slope trick
713C - Sonya and Problem Wihtout a Legend. 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.
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.