Duality in linear programming. Part 2 — in competitive programming

Revision en3, by adamant, 2022-08-09 12:38:27

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 mnemonics

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?

Primal formulation
Dual formulation
Solution

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 formulation
Dual formulation
Solution

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 formulation
Dual formulation
Solution

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:

  1. Change $$$a_k$$$ to $$$v$$$;
  2. 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 formulation
Dual formulation
Solution

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 formulation
Dual formulation
Solution

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 formulation
Dual formulation
Solution

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 formulation
Dual formulation
Solution

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.

Primal formulation
Dual formulation
Solution

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.

Primal formulation
Dual formulation
Solution

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.

Tags tutorial, linear programming, duality

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English adamant 2022-08-09 17:30:20 77
en3 English adamant 2022-08-09 12:38:27 7
en2 English adamant 2022-08-09 02:19:18 1912
en1 English adamant 2022-08-09 02:03:29 29538 Initial revision (published)