Official

G - Unevenness Editorial by en_translator

This problem features what is called Dual Linear Program (LP), and especially cost flow dual.

Prerequisites

We will briefly explain the cost flow dual.

  • The prerequisites here are that the minimum-cost flow problem can be solved fast, and the rough overview on the algorithm itself (the successive shortest path algorithm based on Bellman-Ford algorithm). If you do not know it, we recommend you to learn it with, for instance, a material by hos (in Japanese). (Translator’s note: seems there is a good article on TopCoder blog.)

Linear Programming Problem and its Dual Problem

A Linear Programming Problem (LP) is a problem where the objective function (to be maximized or minimized) is a linear function, and the constraints on the variables are also written as equalities and inequalities on linear functions.
Specifically, it refers to a problem representable using a matrix and vectors in the following form (there are several representation variants). Here, \(A\) is a constant matrix, \(b\) and \(c\) are constant vectors, and \(x\) is the variable vector.

\[ \begin{aligned} &\text{maximize} & &c^{T} x \\ &\text{subject to} & & Ax \leq b\\ & & & x \geq 0 \end{aligned} \]

The dual problem of the problem above refers to the following:

\[ \begin{aligned} &\text{minimize} & &b^{T} y \\ &\text{subject to} & & A^{T}y \geq c\\ & & & y \geq 0 \end{aligned} \]

Corresponded to the dual, the original is called the primal problem.

The primal and dual satisfies the following strongly duality theorem. (Such a property is called strong duality.)

Strong duality problem

If both the primal and dual has a solution that satisfies the constraints (this is called a feasible solution). Then both problems have optimal solutions \(x^\ast\) and \(y^\ast\) with the same optimal value (satisfying \(c^T x^\ast = b^T y^\ast\)).

For more details on the duality and how to take the duals on other LP variants, please refer to the references below (all in Japanese).

Dual Problem of Minimum-Cost Flow Problem

The minimum-cost flow problem can be described as a Linear Programming problem.
We first formalize the problem. Here, instead of an ordinary flow problem with a source and a sink (s-t flow), we formalize it in a generalized form called b-flow, as follows:

There is a directed graph \((V, E)\) with capacity \(c_e\) \((\geq 0)\) assigned to each edge \(e\).
Each vertex \(v\) has a supply of \(b_v\) (which means it has a demand of \(-b_v\) if \(b_v < 0\)).
The cost of flow per unit on edge \(e\) is \(w_e\). Minimize \(\sum_e f_e w_e\), where \(f_e\) the amount of flow on edge \(e\).

This problem can be formalized as an LP as follows. Here, edge \(u\to v\) are denoted as \((u,v)\).

\[ \begin{aligned} &\min. & & \sum_{e \in E} w_e f_e \\ &\mathrm{s.t.} & & \sum_{e=(v,u)\in E} f_e - \sum_{e=(u,v)\in E} f_e = b_v & & (\forall v \in V) \\ & & & f_e \leq c_e & & (\forall e \in E) \\ & & & f_e \geq 0 & & (\forall e \in E) \end{aligned} \]

Let us take the LP dual, assigning \(p_v\) and \(z_e\) to the lines above.

\[ \begin{aligned} &\max. & & \sum_{v \in v} b_v p_v + \sum_{e \in E} c_e z_e \\ &\mathrm{s.t.} & & p_u - p_v + z_e \leq w_e & & (\forall e=(u,v) \in E)\\ & & & z_e \leq 0 & & (\forall e \in E) \end{aligned} \]

Replace \(p_u, p_v\), and \(z_e\) with those multiplied by \(-1\).

\[ \begin{aligned} &\max. & & -\sum_{v \in v} b_v p_v - \sum_{e \in E} c_e z_e \\ &\mathrm{s.t.} & & p_v - p_u - z_e \leq w_e & & (\forall e=(u,v) \in E)\\ & & & z_e \geq 0 & & (\forall e \in E) \end{aligned} \]

Then notice that, when \(p_u\) and \(p_v\) are fixed, it is optimal that \(z_e\) takes on \(\max(p_v - p_u - w_e, 0)\). Thus we can remove \(z_e\) to turn it into the following problem:

\[ \begin{aligned} &\max. & & -\sum_{v \in v} b_v p_v - \sum_{e =(u,v)\in E} c_e \max(p_v - p_u - w_e, 0) \\ \end{aligned} \]

Multiplying the objective function by \(-1\) we arrive at the following minimization problem:

\[ \begin{aligned} &\min. & & \sum_{v \in v} b_v p_v + \sum_{e =(u,v)\in E} c_e \max(p_v - p_u - w_e, 0) \\ \end{aligned} \]

This is the formalization of what is known as the dual of minimum-cost flow problem (costs flow dual). (Academically it is called the minimum-cost tension problem, although the formalization is slightly different.) \(p_v\) is called the potential.

We can interpret the LP of the cost flow dual as the following problem:

We need to assign a value \(p_v\) to each vertex \(v\).
Each vertex \(v\) incurs a cost of \(b_v p_v\).
Each edge \(e=(u,v)\) incurs a cost of the sum of \(c_e \max(0, p_v - p_u - w_e)\).
Minimize the cost.

By the way, a polyline that is convex with respect to \(x\) (called a piecewise linear convex function) can be written as a linear combination of \(\max(0, x - w)\) and \(\max(0, w - x)\).
Thus, the following problem can be represented as a LP for a cost flow dual, and the optimal value of the objective function can be computed with the minimum-cost flow algorithm.

We need to assign a value \(p_v\) to each vertex \(v\).
Each vertex \(v\) incurs a cost of \(b_v p_v\).
Each edge \(e=(u,v)\) incurs a cost of \(F_e(p_v-p_u)\), where \(F_e(x)\) is a piecewise linear convex function.
Minimize the cost.

To wrap up the discussion so far, we have the following facts:

  • A cost flow dual is a problem to minimize the cost when a cost is incurred according to a convex function of the difference \(p_v - p_u\).
  • A cost flow dual can be turned into a minimum-cost flow problem by taking its LP dual.
  • The optimal values of the primal and the dual coincide, so the optimal value of a cost flow dual can be found using the minimum cost flow algorithm.

Now the following question arises:

  • How can one reconstruct the potentials that gives the optimal solution for the cost flow dual?

This is not obvious, because the minimum-cost flow algorithm computes the optimal solution for the cost-flow problem and flows \(f_e\) that give the optimal solution, but not the potentials \(p_v\) themselves. (That said, minimum-cost flow algorithms usually internally computes \(p_v\) too. Details will be explained later)

This issue can be resolved using the conditions called complementary conditions.

Complementary Condition

We referred to an article by Taihei Oki (in Japanese) to write this section.

We will describe the condition LP’s complementary condition. Let us first recall the primal and dual of an LP:

  • Primal problem

\[ \begin{aligned} &\text{maximize} & &c^{T} x \\ &\text{subject to} & & Ax \leq b\\ & & & x \geq 0 \end{aligned} \]

  • Dual problem

\[ \begin{aligned} &\text{minimize} & &b^{T} y \\ &\text{subject to} & & A^{T}y \geq c\\ & & & y \geq 0 \end{aligned} \]

Here,

  • since \(c \leq A^T y\) and \(x \geq 0\) we have \(c^{T} x \leq (A^T y)^T x = y^T A x\);
  • since \(Ax \leq b\) and \(y \geq 0\) we have \(y^T A x \leq y^T b = b^T y\);

so

\[c^T x \leq y^T A x \leq b^T y,\]

which means that (the objective function’s value of the primal) \(\leq\) (the objective function’s value of the dual). This is called the weak duality theorem or weak duality.
By the way, we already explained a stronger theorem than the weak duality theorem, namely the strong duality theorem, which claims that optimal solutions \(x\) and \(y\) satisfy \(c^T x = b^T y\). Therefore, when \(x\) and \(y\) are optimal solutions, we have

\[c^T x = y^T A x = b^T y.\]

Now let \(x\) be a length-\(n\) vector, and \(y\) be a length-\(m\) vector. Deforming \(c^T x = y^T A x\) yields:

\[\sum_{i=1}^n((A^T y)_i - c_i) x_i = 0.\]

Here we have \(A^T y \geq c\) and \(x \geq 0\), so the left hand side is obviously non-negative. Thus, we obtain the following conditions:

  • \(x_i = 0\) or \((A^T y)_i = c_i\) for all \(i=1,2,\dots,n\).

Likewise, deforming \(y^T A x = b^T y\) eventually yields

  • \(y_j = 0\) or \((Ax)_j = b_j\) for all \(j=1,2,\dots,m\).

These are called the complementary conditions.
Also, if solutions \(x\) and \(y\) satisfy the complementary conditions, then \(c^T x = y^T A x = b^T y\) holds, which evidently implies \(x\) and \(y\) are optimal solutions. Therefore, \(x\) and \(y\) are optimal solutions if and only if the complementary conditions hold. This is called the complementary theorem.

Consider finding the optimal-solution set of the primal problem using the complementary theorem. Suppose that we have obtained an optimal solution \(y\) of the dual. Then by the complementary theorem, \(x\) is an optimal solution if and only if all the following hold:

  • For all \(i=1,2,\dots,n\), if \((A^T y)_i \gt c_i\) then \(x_i = 0\).
  • For all \(j=1,2,\dots,m\), if \(y_j \gt 0\) then \((Ax)_j = b_j\).

Thus, an optimal solution for \(x\) satisfies the equalities obtained by turning some of the inequality constraints into equalities. Specifically, if an inequality holds in the dual problem, then the corresponding condition in the primal becomes the quality. This way, one can reconstruct the conditions that optimal solutions for the primal satisfy based on an optimal solution for the dual problem.

Reconstruction of Solution to Cost Flow Dual

Now let us reconstruct the potentials that are a solution for the cost flow dual using the complementary theorem.
Again, here are the LPs when the Cost Flow Dual are considered the primal. (Some \(-1\) factors are ignored because they are inessential.)

  • Primal problem

\[ \begin{aligned} &\min. & & \sum_{v \in v} b_v p_v + \sum_{e \in E} c_e z_e \\ &\mathrm{s.t.} & & p_v - p_u - z_e \leq w_e & & (\forall e=(u,v) \in E)\\ & & & z_e \geq 0 & & (\forall e \in E) \end{aligned} \]

  • Dual problem

\[ \begin{aligned} &\min. & & \sum_{e \in E} w_e f_e \\ &\mathrm{s.t.} & & \sum_{e=(v,u)\in E} f_e - \sum_{e=(u,v)\in E} f_e = b_v & & (\forall v \in V) \\ & & & f_e \leq c_e & & (\forall e \in E) \\ & & & f_e \geq 0 & & (\forall e \in E) \end{aligned} \]

Applying the complementary theorem, we obtain the following conditions regarding \(p_v\) and \(z_e\):

  • \(z_e = 0\) for all \(e\) with \(f_e \lt c_e\);
  • \(p_v - p_u - z_e = w_e\) for all \(e=(u,v)\) with \(f_e \gt 0\).

After eliminating \(z_e\), we arrive at the following:

  • \(p_v - p_u \leq w_e\) for all \(f_e \lt c_e\) with \(e=(u,v)\).
  • \(p_u - p_v \leq -w_e\) for all \(f_e \gt 0\) with \(e=(u,v)\).

It is sufficient to find potentials \(p_v\) that satisfy these conditions. Finding one such \(p_v\) is widely known as 牛ゲー (in Japanese community; literally “cow game” but rather like “cow trick,” originating from POJ No.3169 “Layout”), which is the dual of a shortest path problem. Specifically, \(p_v\) can be found by the following algorithm:

  • Consider a graph with an edge \(b \to a\) of weight \(w_c\) for each condition in the form \(p_a - p_b \leq w_c\).
  • Compute the distance from an arbitrary starting vertex using Bellman-Ford algorithm.
  • Solutions \(p_v\) can be obtained if the graph does not have a negative cycle.

However, “if the graph does not have a negative cycle” is problematic. Does the graph constructed by the procedure above really have no negative cycles?

Here, the constructed graph has the following edges:

  • Edge \(u \to v\) of weight \( w_e\) if \(0 \leq f_e \lt c_e\)
  • Edge \(v \to u\) of weight \(-w_e\) if \(0 \lt f_e \leq c_e\)

Actually, this graph coincides with the residual graph that is internally constructed in the minimum-cost flow algorithm!
Here, it is known that cost flows \(f_e\) are optimal if and only if the residual graph does not have a negative cycle. Thus, if \(f_e\) are optimal solutions, the graph does not contain a negative cycle, and we can assert the validity of the algorithm to reconstruct potentials using Bellman-Ford algorithm.

Let us wrap up the discussion so far once again:

  • A cost flow dual is a problem to minimize the cost when a cost is incurred according to a convex function of the difference \(p_v - p_u\).
  • A cost flow dual can be turned into a minimum-cost flow problem by taking its LP dual.
  • The optimal values of the primal and the dual coincide, so the optimal value of a cost flow dual can be found using the minimum cost flow algorithm.
  • By the complementary theorem, a solution \(p_v\) of the cost flow dual can be obtained from the solution \(f_e\) of the minimum-cost flow problem using Bellman-Ford algorithm.

In the explanation so far, we did not dig into the internals of algorithms to find the minimum cost flow. Indeed, in AtCoder environment one can compute it without knowing the details of the algorithm but with AtCoder Library (ACL).
Nevertheless, as we briefly mentioned above, some algorithms to find the minimum cost flow is capable of finding not only the solution for the minimum-cost flow problem \(f_e\) but also the cost flow dual \(p_v\). There are several such minimum-cost flow algorithms; here we introduce Primal-Dual algorithm, which is adopted in ACL too.

Primal-Dual Algorithm

For simplicity, we explain how to find the minimum-cost flow problem with a single source and sink on a graph without negative edges (edges with negative cost).

  • Cases with an negative edge can be handled with the trick explained in, for example, snuke’s article (in Japanese).
  • To find b-flow, you can add two vertices \(s\) and \(t\) and appropriate edges to boil it down to s-t flow.

Primal-Dual algorithm is a kind of Successive Shortest Path algorithm (SSP).

  • Note that some references introduces Primal-Dual algorithm as an algorithm different from a SSP algorithm. In this article, we define the SSP using the Dijkstra’s algorithm as the Primal-Dual algorithm.

First of all, we roughly review the SSP algorithm using Bellman-Ford algorithm.

  • Initially, set the flow \(f_e\) of all edges to \(0\).
  • While the flow is less than \(F\), do the following:
    • Find the shortest \(s \to t\) on the residual graph (with respect to the cost).
    • Push a unit flow according to one of the shortest paths found.

In this algorithm, there will always be a negative edges in the residual graph (except for the first iteration), so Bellman-Ford algorithm is required to find the shortest path. Thus, the overall complexity is \(\mathrm{O}(F N M)\), where \(N\) and \(M\) are the number of vertices and edges, respectively.

To improve the complexity to find the shortest path, we utilize the potentials \(p_v\). By the residual theorem described above, the residual graph satisfies the following property:

  • there exist potentials \(p_v\) such that:
    • for all edges \(u \to v\) of cost \(w_{uv}\), we have \(w_{uv}+p_u-p_v \geq 0\).

Suppose that we know the potentials \(p_v\) of the residual graph. In SSP, what we want to find is a shortest path from vertex \(s\) to vertex \(t\).
Here, consider the graph where the cost of the residual graph is replaced from \(w_{uv}\) with \(w_{uv}+p_u-p_v\). (We call this simplified cost.)

Then, the simplified cost of a path \(v_0 \to v_1 \to v_2 \to \dots \to v_k\) is

\[ \sum_{i=0}^{k-1} w_{v_i v_{i+1}} + p_{v_i} - p_{v_{i+1}} = \left(\sum_{i=0}^{k-1} w_{v_i v_{i+1}}\right) + p_{v_0} - p_{v_k}, \]

which is dependent only on the length of the path itself and the potentials of the starting and ending vertices. Thus, an \(s-t\) shortest path can be find using the simplified cost.
Here the key is that, by the non-negativity of the simplified cost, the s-t shortest path based on the simplified costs can be found using Dijkstra’s algorithm instead of Bellman-Ford algorithm.

Since the edges in the residual graph changes every time flow is pushed, the potentials \(p_v\) also needs to be updated accordingly. To update them, in fact one can simply add the \(s-t\) shortest distance with respect to the simplified costs to the potential \(p_v\) every time flow is pushed. (The proof is in a material by Yoshio Okamoto (in Japanese), so we do not explain it here.)

After all, we have the following algorithm:

  • Initially, let the flow \(f_e\) of every edge and the potential \(p_v\) of every vertex be \(0\).
  • While the flow amount is less than \(F\), repeat the following:
    • Find an \(s \to t\) shortest path on the residual graph (with respect to the simplified costs).
    • Push a unit flow on the shortest path found.
    • Add the shortest distance with respect to the simplified costs to each vertex (to update \(p_v\)).

The algorithm runs like following: improve the solution for the primal problem \(\to\) improve the solution for the dual problem \(\to\) improve the solution for the primal problem \(\to\) \(\dots\), where the solutions for the primal and the dual are improved alternately. That is why the algorithm is called Primal-Dual algorithm. The complexity of this algorithm is \(\mathrm{O}(F(N+M)\log(N+M))\) because we are using Dijkstra’s algorithm, and it runs faster than the SSP algorithm using bellman-Ford algorithm.

As a side note, since the Primal-Dual algorithm has \(P\) in its computational complexity, we cannot guarantee fast execution for graphs with large capacities. By using what is called capacity scaling, the improved version of Primal-Dual algorithm, the number of times Dijkstra’s algorithm is run can be reduced from \(\mathrm{O}(F)\) to \(\mathrm{O}(M \log F)\). For more details, please refer to an article by misawa.
Also, competitive programmers who prepare a bunch of library typically uses cost scaling or network simplex method, and practically these two algorithms seems to be far faster than the others. (Reference on arxiv)

Let us wrap up the discussion so far again:

  • A cost flow dual is a problem to minimize the cost when a cost is incurred according to a convex function of the difference \(p_v - p_u\).
  • A cost flow dual can be turned into a minimum-cost flow problem by taking its LP dual.
  • The optimal values of the primal and the dual coincide, so the optimal value of a cost flow dual can be found using the minimum cost flow algorithm.
  • A solution \(p_v\) of the cost flow dual can be found in the following ways:
    • By the complementary theorem, a solution \(p_v\) of the cost flow dual can be obtained from the solution \(f_e\) of the minimum-cost flow problem using Bellman-Ford algorithm.
    • Compute \(f_e\) and \(p_v\) at the same time by using algorithms like minimum-cost flow problem.

Based on the knowledge so far, we will explain the solution to the original problem.

Solution

We will now explain the solution. The outline is as follows: the problem can be formalized as a variant of a flow cost dual problem, so it can be boiled down to the minimum cost flow problem, and the solution can be found by reconstructing the potentials.

Let \(K = \frac{P}{Q}\). Regard the grid as a graph \((V, E)\) with \(N^2\) vertices and \(2N(N-1)\) edges. Let \(p_v\) be the final value written on vertex \(v\), then the answer is the optimal value and an optimal solution for the following LP:

\[ \begin{aligned} &\min. & &\sum_{e=(u,v)\in E} \vert p_v - p_u \vert\\ &\mathrm{s.t.}& &\sum_{v \in V} \vert p_v - A_v\vert \leq K \end{aligned} \]

Regard each edge not as an undirected graph, but as two bidirectional edges. (In other words, we make the edges directed and double them.) Then we can deform the expressions as follows. Here, \((u, v)\) denotes the edge going from \(u\) to \(v\).

\[ \begin{aligned} &\min. & &\sum_{e=(u,v)\in E} \max(p_v - p_u, 0) \\ &\mathrm{s.t.}& &\sum_{v \in V} \left(\max(p_v - A_v,0)+\max(A_v - p_v, 0)\right)\leq K \end{aligned} \]

Denoting the \(\max\) expression by \(a_e, x_v\), and \(y_v\), in order, we can write it as follows:

\[ \begin{aligned} &\min. & & \sum_e a_e \\ &\mathrm{s.t.}& & p_v - p_u - a_e \leq 0& & (\forall e=(u,v) \in E)\\ & & & p_v - x_v \leq A_v & & (\forall v \in V)\\ & & & -p_v - y_v \leq -A_v& & (\forall v \in V)\\ && &\sum_v \left( x_v + y_v \right)\leq K\\ & & & a_e, x_v, y_v \geq 0 \\ \end{aligned} \]

We take the dual. We assign variables \(f_e, z_v, w_v,\lambda\) to the lines above in order to obtain:

\[ \begin{aligned} &\max. & & \sum_{v \in V} A_v(z_v - w_v) + K \lambda \\ &\mathrm{s.t.}& & \sum_{e=(u,v)\in E}f_e - \sum_{e=(v,u)\in E}f_e + z_v - w_v = 0 & & (\forall v \in V)\\ & & &-f_e \leq 1 & & (\forall e \in E)\\ & & &-z_v + \lambda \leq 0 & & (\forall v \in V)\\ & & &-w_v + \lambda \leq 0 & & (\forall v \in V)\\ & & &f_e, z_v, w_v, \lambda \leq 0 \end{aligned} \]

We multiply it by \(-1\) to make it a minimization problem. We also replace \(f_e,z_v,w_v,\lambda\) with those multiplied by \(-1\):

\[ \begin{aligned} &\min. & & \sum_v A_v(z_v - w_v) + K \lambda\\ &\mathrm{s.t.}& & \sum_{e=(u,v)\in E}f_e - \sum_{e=(v,u)\in E}f_e + z_v - w_v = 0 & & (\forall v \in V)\\ & & &0 \leq f_e \leq 1 & &(\forall e \in E)\\ & & &0 \leq z_v \leq \lambda & & (\forall v \in V)\\ & & &0 \leq w_v \leq \lambda & & (\forall v \in V)\\ \end{aligned} \]

This way, the problem is boiled down to a minimum cost flow problem. Specifically, let \(f(\lambda)\) be the cost for the following minimum cost flow problem, then we are asked to minimize \(U = f(\lambda) + K \lambda\).

There are vertex \(S\) and vertices \(v \in V\). Add an edge from vertex \(S\) to vertex \(v\) with capacity \(\lambda\) and cost \(A_i\). Add an edge from vertex \(v\) to vertex \(S\) with capacity \(\lambda\) and cost \(-A_i\). Add an edge from vertex \(u\) to vertex \(v\) with capacity \(1\) and cost \(0\). What is the minimum cost of minimum-cost cycle flow?

Here, notice that \(\lambda\) takes on real values, which means assuming the integrality of \(\lambda\) and performing a ternary search is a wrong approach. However, one can assert that the slope of \(f(\lambda)\) changes at a finite number of points, and the denominators of such \(\lambda\) are sufficiently small. Hereinafter, we will prove that fact.

Let us focus on \(f(\lambda)\) for a fixed \(\lambda\), and the solutions for the dual (minimum cost flow) and for the primal (potentials).

First, \(f(\lambda)\) is a convex function.

(Proof) Let \(x_1\) and \(x_2\) be the answer to the dual LP for fixed \(\lambda=\lambda_1, \lambda_2\), respectively. Also, let \(0 \leq \alpha \leq 1\).
Let \(x_3 = \alpha x_1 + (1-\alpha) x_2\). Then, since the constraints are all linear, \(x_3\) is a feasible solution. Also, the \(\lambda\) here is \(\alpha \lambda_1 + (1-\alpha) \lambda a_2\). Moreover, denoting by \(\mathrm{DLP}(x)\) the value when \(x\) is assigned to the dual LP, we have

\[\mathrm{DLP}(x_3) = \alpha \mathrm{DLP}(x_1) + (1-\alpha) \mathrm{DLP}(x_2).\]

Therefore, we arrive at

\[ \begin{aligned} f(\alpha \lambda_1 + (1-\alpha) \lambda a_2) &\leq \mathrm{DLP}(x_3)\\ &= \alpha \mathrm{DLP}(x_1) + (1-\alpha) \mathrm{DLP}(x_2) \\ &= \alpha f(\lambda_1) + (1-\alpha) f(\lambda_2), \end{aligned} \]

which implies that \(f(\lambda)\) is convex, proving what we wanted. (End of proof)

Furthermore, we claim a stronger property: \(f(\lambda)\) is a piecewise linear function with the slopes being integers.

(Proof) we already know that \(f(\lambda)\) is convex, so it is sufficient to show that \(\displaystyle \lim_{\Delta\to +0} \frac{f(\lambda+\Delta)-f(\lambda)}{\Delta}\) is an integer for a fixed \(\lambda\).
Consider the residual graph of the minimum cost flow. Changing \(\lambda\) to \(\lambda + \Delta\) (where \(\Delta\) is sufficiently smaller than the capacities of the edges in the residual graph) means adding the following edges to the residual graph for \(\lambda\):

  • edge from \(S\) to \(v\) with capacity \(\Delta\) and cost \(A_i\);
  • edge from \(v\) to \(S\) with capacity \(\Delta\) and cost \(-A_i\).

Here, the new negative cycles have the following form: \(S \to u \to \dots \to v \to S\), where at least one of edge \(S\to u\) and \(v\to S\) must have a capacity \(\Delta\). Also, the capacity of the edges other than the added one is far larger than \(\Delta\), so the amount of flow in the negative cycle is \(\Delta\). Hence, repeatedly pushing flow to negative cycles as long as there is no more negative cycle incurs the cost of the form \((integer) \times \Delta\), which shows that \(\displaystyle \lim_{\Delta\to +0} \frac{f(\lambda+\Delta)-f(\lambda)}{\Delta}\) is an integer. (End of proof)

Moreover, by the form of the cost flow, one can assert that the slope of \(f(\lambda)\) is between \(-N^2 \max(A)\) and \(0\), inclusive. Thus, \(f(\lambda)\) is a function consisting of a finite number of line segments.

By the discussion so far, one can divide the domain \([0,\infty)\) of \(\lambda\) into several segments according to the slopes of \(f(\lambda)\); that is, one can take \(\lambda_0, \lambda_1, \dots, \lambda_n\) and \(K_0, K_1, \dots, K_n\) so that:

  • The slope of \(f(\lambda)\) within \((0 = \lambda_0, \lambda_1)\) is \(-K_0\).
  • The slope of \(f(\lambda)\) within \((\lambda_1, \lambda_2)\) is \(-K_1\).
  • The slope of \(f(\lambda)\) within \((\lambda_2, \lambda_3)\) is \(-K_2\).
  • \(\vdots\)
  • The slope of \(f(\lambda)\) within \((\lambda_n, \infty)\) is \(-K_n = 0\).

Recall that the original LP asked to minimize \(U = f(\lambda)+K \lambda\). (The sign is flipped from the original problem, but we ignore it.) By the shape of \(f(\lambda)\), we have the following facts:

  • If \(K \gt K_0\), it takes the minimum value at \(\lambda = \lambda_0\).
  • If \(K = K_0\), it takes the minimum value at \(\lambda_0 \leq K \leq \lambda_1\).
  • If \(K_0 \gt K \gt K_1\), it takes the minimum value at \(\lambda = \lambda_1\).
  • If \(K_{n-1} \gt K \gt K_n\), it takes the minimum value at \(\lambda = \lambda_n\).
  • \(\vdots\)
  • If \(K = K_n = 0\), it takes the minimum value at \(\lambda_n \leq \lambda\).

Regarding the potential that can be obtained by pushing cost flow, consider the cost of the operations required to make the solution to the primal coincide with the potentials (which we simply refer to as the cost). Since the potential of the cost flow when taking a \(\lambda\) that minimizes \(U\) for some \(K\) is a solution for the primal problem, the \(\lambda\) for the fixed \(\lambda\) and the cost \(C\) of the potentials must have the following relation: \(U\) takes on the minimum value at \(\lambda\) when \(K=C\). Thus, the cost \(C\) have the following properties:

  • \(C \geq K_0\) for \(\lambda = \lambda_0 = 0\).
  • \(C=K_0\) for \((\lambda_0, \lambda_1)\).
  • \(K_0 \geq C \geq K_1\) for \(\lambda = \lambda_1\).
  • \(C=K_1\) for \((\lambda_1, \lambda_2)\).
  • \(\vdots\)
  • \(C=K_n=0\) for \((\lambda_n, \infty)\).

By the way, since the edge weights in the cost flow are integers, the potentials obtained by solving the shortest path problem on the residual graph are also integers, and the objective function \(U\) are integers too. Thus, the minimum value \(f(\lambda_i) + K_i \lambda_i\) of objective function \(U\) for \(K=K_i\) is an integer. Together with the fact that \(f(\lambda)\) within \((\lambda_i, \lambda_{i+1})\) can be represented in the form of \(y=-K_i\lambda+f(\lambda_i) + K_i \lambda_i\), every segment occurring in \(f(\lambda)\) turns out to be in the form of \(y=(integer)\lambda+(integer)\).

Thus, \(\lambda_i\), the position where the slopes change, is an intersection of \(y=-K_i\lambda+f(\lambda_i) + K_i \lambda_i\) and \(y=-K_{i+1}\lambda+f(\lambda_{i+1}) + K_{i+1} \lambda_{i+1}\), so the denominator can be proven not greater than the difference of \(K_i\), or \(N^2 \max(A)\). Also, by the form of the minimum cost flow, the slope of \(f(\lambda)\) for \(\lambda \geq 4\) is \(0\), so the numerator can also be bonded by \(4N^2 \max(A)\). Hence, the numerator and denominator of \(\lambda_i\) has been proven to be sufficiently small.

  • By the way, we have a conjecture that the numerators numerators and denominators can be bounded even more strictly by \(\mathrm{O}(N^2)\) based on experiments, but we could not proved it yet.

We will construct the solution based on the discussions so far. Consider performing a binary search on Stern-Brocot tree for \(\lambda\).

  • Binary search on Stern-Brocot tree is already featured in ABC333-G, so we do not describe it in detail. You may also refer to an editorial by MMNMM (in Japanese).
  • Under the constraints of this problem, the searching algorithm in which you descend the tree step by step without performing binary search on the tree runs probably faster under the constraints this time, and the implementation is simpler.

The criteria in the binary search is whether the cost of the potentials in the cost flow for a fixed \(\lambda\) is less than \(K\) or not.

  • even if \(\lambda\) is a rational number, one can multiply all the capacities by the denominator to make the capacities integers, which allows us to apply ordinary cost-flow algorithms.

By performing binary search where the denominator goes up to \(\mathrm{O}(N^2 \max(A))\), one can find

  • \(\lambda_L\): the maximum fraction for which the potentials’ cost is greater than or equal to \(K\)
  • \(\lambda_R\): the maximum fraction for which the potentials’ cost is less than\(K\)

as well as the costs of the flow \(f(\lambda_L)\) and \(f(\lambda_R)\) and potentials \(B(\lambda_L)\) and \(B(\lambda_R)\).

  • As an edge case, the cost of the potential can be always less than \(K\). In such cases, one can print \(U=0\) and \(B=B(0)\).

Now we can find \(U\) and \(B\). It is relatively obvious that \(U\) can be found as

\[\min(f(\lambda_L) + K \lambda_L, f(\lambda_R) + K \lambda_R).\]

On the other hand, in fact \(B\) can be found as the weighted average of \(B(\lambda_L)\) and \(B(\lambda_R)\) so that the cost becomes \(k\). (The proof is not simple, but all that needed is thorough caseworks, so we omit it here.) The problem can be solved by implementing the algorithm described so far.

Now we consider the complexity. The flow of the cost flow is \(\mathrm{O}(\lambda N^2)\), and there are \(\mathrm{O}(N^2)\) edges. Since the numerator and denominator of \(\lambda\) is \(\mathrm{O}(N^2 \max(A))\) and we are multiplying the capacities by the denominator to make it integer flow, the cost flow and the potentials can be found in \(\mathrm{O}(N^6 \max(A) \log N)\) time per iteration. (Appropriate removal of negative edges is required). This iterations is performed \(\log (N^2\max(A))\) times through the binary search, so the overall complexity is \(\mathrm{O}(N^6 \max(A) \log N \log (N\max(A)))\). (Depending on the flow algorithm and the approach in binary search, the sum of exponents of \(N\) and \(\max(A)\) can become from \(4\) to \(10\), but the constant factor is so small that all of them will probably be accepted.)
We also roughly evaluate the errors in \(U\). \(U\) itself can be found precisely as a rational number, so that the number of operations subject to errors required to print the answer is two casts from integers to decimals and one division of integer. Denoting by \(\varepsilon\) the machine epsilon (which is \(2^{-53}\) for double and \(2^{-65}\) for long double), the relative error can be bounded by \(3\varepsilon\), which is less than the tolerated error. (Nonetheless, the error for double has almost no margin than the requirements, so we recommend you to use long double type. Also, if you turn \(K\) into decimals before solving, computing \(U\) may required additions of values with different signs, which may cause a cancellation of significant digits and WA (Wrong Answer) verdict, so be careful.)
As a side note, we set an uncanny error tolerance and gave \(K\) as a rational number in order to prevent scipy.optimize.linprog and ortools.linear_solver from being accepted due to the errors. (Ordinary Linear Programming solver runs on double-precision floating point type, so probably it fails. If your LP solver supports quadruple-precision floating point type like __float128, your answer might be accepted.)

Exercises

Here are the past problems in ABC that can be solved with LP dual or cost flow dual, may it be intentional or unintentional solution. Use them as exercises.

posted:
last update: