This blog is adapted from a previous blog I wrote in my personal blog. I thought it would be good to share the relevant parts here. If you want to read my personal blog, go ahead, but I will warn you that it is a shitpost blog.

The problems discussed in this blog is:

• ARC085C
• ABC225G
• ABC259G
• ABC193F
• ARC142E

You can attempt these problems to see if you can figure out how to wrangle them into min-cut formulation knowing that they are min-cut.

I have been told by a lot of old people that in the heydays of Topcoder it was flow meta. Those old people will obviously be really good at flow modelling since it was necessary but now I feel like a complete noob at flow compared to them. During OCPC I just watched 244mhq do flow problems and all I could do was go 👁️👄👁️👍

Unfortunately, those heydays are over and flow barely appears in competitive programming. Furthermore, I don't know how to use Topcoder to access their wealth of flow problems... perhaps there are 120230492384 good examples of flow problems in Topcoder but I'm not aware of them.

So here is my attempt at writing a systematic way of solving problems where we care about modelling min-cut. This blog does not assume any prerequisite knowledge, expect knowing:

• the minimum cut is equal to the maximum flow
• how to use a maximum flow library KACTL Dinic or ACL max flow

If you want to read up more on this subject, I cannot recommend enough the blogs on Dinitz's and min cut by -is-this-fft-.

Now there are two ways to define a cut of a flow network.

1. A cut is a set of edges such that removing those edges will not allow us to find a path $$$s \to t$$$.
2. If we split the vertices of the flow network into disjoint sets $$$X$$$ and $$$Y$$$ such that $$$s \in X$$$ and $$$t \in Y$$$, then a cut is all the edges $$$(u,v)$$$ such that $$$u \in X$$$ and $$$v \in Y$$$.

For the longest time, I was stuck thinking about the cut of a flow network in terms of definition 1. But it turns out that using definition 2 is a lot better for modelling purposes. Why? Because we can solve the following problem.

You need to construct a binary string $$$S$$$ of length $$$n$$$, the cost of the binary string is defined as follows:

• If $$$S_i = \texttt{0}$$$, you get $$$A_i$$$ penalty
• If $$$S_i = \texttt{1}$$$, you get $$$B_i$$$ penalty
• If $$$S_i = \texttt{1}$$$ and $$$S_j = \texttt{0}$$$, you get $$$C_{i,j}$$$ penalty

So basically $$$i \in X$$$ has $$$S_i = \texttt{1}$$$ and $$$i \in Y$$$ has $$$S_i = \texttt{0}$$$. Then we construct the following flow graph:

• $$$s \to i$$$ with cost $$$A_i$$$
• $$$i \to t$$$ with cost $$$B_i$$$
• $$$i \to j$$$ with cost $$$C_{i,j}$$$

Then our min cut corresponds to the answer to our problem. For some reason, my brain finds this easier to work with than thinking about $$$X$$$ and $$$Y$$$.

In the above formula, I have assumed that all of $$$A,B,C$$$ are non-negative. Please note that we cannot put negative weights into a flow graph and expect the max flow to spit out the correct answer.

So what should we do if some of $$$A,B,C$$$ are negative? Notice that we can add a constant $$$M$$$ to both $$$A_i$$$ and $$$B_i$$$ as long as we subtract $$$M$$$ from our answer later. So we can transform the problem to one where $$$A_i$$$ and $$$B_i$$$ are non-negative. Unfortunately, we need to force a constraint on $$$C_{i,j}$$$ being non-negative as I don't know how to handle it when it is negative.

Therefore, in the below solutions, I will liberally allow $$$A$$$ and $$$B$$$ to take negative values. Just remember to properly correct them when setting up your flow network.

We can write all flow networks in our binary string formulation and we can write all binary string formulations as flow networks as long as $$$C_{i,j} \geq 0$$$. So we will forget that we are even working with flow networks and formulate our problem entirely using this binary string formulation. It is like when solving problems in 2-SAT, you do not need to care that we are attacking it with SCCs to transform the problem into one about 2-SAT. Same thing here.

For the rest of the blog, we will be solving min-cut problems by transforming them into our binary string formulation.

Project Selection Problem

The project selection problem is described here in Wikipedia. In short, you are given $$$n$$$ projects and $$$m$$$ machines. Each project has profit $$$p_i$$$ and machine machine has cost $$$q_i$$$. Each project has a set of machines that you must buy to complete the project. (Each machine, once purchased, can be used by all projects that require it.)

Let the indices of our binary string be the set of all projects and machines. $$$S_i = \texttt{0}$$$ means we take the project/buy the machine and $$$S_i = \texttt{1}$$$ means we do not take the project/do not buy the machine.

To handle the profit of taking project $$$i$$$, we add the constraint:

• If $$$S_i = \texttt{1}$$$, we get $$$-p_i$$$ penalty

To handle the cost of buying machine $$$i$$$, we add the constraints:

• If $$$S_i = \texttt{1}$$$, we get $$$q_i$$$ penalty

If $$$i$$$ is a project and $$$j$$$ is a machine and getting the money for project $$$i$$$ requires buying machine $$$j$$$, then we have the constraint:

• If $$$S_i = \texttt{1}$$$ and $$$S_j = \texttt{0}$$$, we get a $$$\infty$$$ penalty

So we have transformed this problem accurately into our binary string formulation and we can solve it using min cut.

ARC085C

Let $$$S_i = \texttt{0}$$$ if we don't smash gem $$$i$$$ and $$$S_i = \texttt{1}$$$ if we smash gem $$$i$$$.

Then the costs are as follows:

• If $$$S_i = \texttt{0}$$$, we pay $$$-A_i$$$ penalty.
• If $$$i$$$ is a factor of $$$j$$$ and $$$S_i=\texttt{1}$$$ and $$$S_j = \texttt{0}$$$, we pay $$$\infty$$$ penalty.

ABC225G

There are 2 slightly different ways to do this problem.

For the first way, we can observe that we can uniquely identify all / diagonal by their bottom left corner and all \ diagonals by their bottom right corner. Then $$$S_{(i,j)} = \texttt{1}$$$ if we draw an X inside cell $$$(i,j)$$$.

Then the costs are as follows:

• If $$$S_{(i,j)} = \texttt{1}$$$, we pay $$$-A_{(i,j)}$$$ penalty
• If $$$S_{(i,j)} = \texttt{1}$$$ and $$$S_{(i+1,j-1)} = \texttt{0}$$$, we pay $$$C$$$ penalty
• If $$$S_{(i,j)} = \texttt{1}$$$ and $$$S_{(i+1,j+1)} = \texttt{0}$$$, we pay $$$C$$$ penalty

For the second way, consider paying $$$A_{(i,j)}-2C$$$ if you draw X on tile $$$(i,j)$$$ and then you get a refund of cost $$$C$$$ if there are X on both tiles $$$(i,j)$$$ and $$$(i+1,j-1)$$$ in addition to X on both tiles $$$(i,j)$$$ and $$$(i+1,j+1)$$$.

So let $$$S_{(i,j),-1}=\texttt{1}$$$ mean that we got the refund for placing X on both tiles $$$(i,j)$$$ and $$$(i+1,j-1)$$$ while $$$S_{(i,j),1}=\texttt{1}$$$ means that we got the refund for placing X on both tiles $$$(i,j)$$$ and $$$(i+1,j+1)$$$.

Then $$$S_{(i,j)} = \texttt{1}$$$ means that we placed X on the tile $$$(i,j)$$$.

Then the costs are as follows:

• If $$$S_{(i,j)} = \texttt{1}$$$, we pay $$$-A_{(i,j)}+2C$$$ penalty
• If $$$S_{(i,j),\pm 1} = \texttt{1}$$$, we pay $$$-C$$$ penalty
• If $$$S_{(i,j),\pm 1} = \texttt{1}$$$ and $$$S_{(i,j)}=\texttt{0}$$$, we pay $$$\infty$$$ penalty
• If $$$S_{(i,j),\pm1 } = \texttt{1}$$$ and $$$S_{(i+1,j\pm 1)}=\texttt{0}$$$, we pay $$$\infty$$$ penalty

Flipping the Constraints

Sometimes, the "natural" constraints are of the form:

• If $$$S_i = \texttt{0}$$$, you get $$$A_i$$$ penalty
• If $$$S_i = \texttt{1}$$$, you get $$$B_i$$$ penalty
• If $$$S_i = \texttt{1}$$$ and $$$S_j = \texttt{1}$$$, you get $$$C_{i,j}$$$ penalty (**PAY ATTENTION**: we have $$$S_j = \texttt{1}$$$ of $$$S_j = \texttt{0}$$$)

How we will convert them into the format needed in our binary string problem above is that realize that if we can split the indices into disjoint sets $$$X$$$ and $$$Y$$$ such that for all constraints $$$C_{i,j} \neq 0$$$ we have $$$i \in X$$$ and $$$j \in Y$$$, then we convert this back into original binary string problem by "flipping" everyone in $$$Y$$$. Specifically:

• If $$$S_i =\texttt{0}$$$ and $$$i \in X$$$, you get $$$A_i$$$ penalty
• If $$$S_i = \texttt{1}$$$ and $$$i \in X$$$, you get $$$B_i$$$ penalty
• If $$$S_i =\texttt{1}$$$ and $$$i \in Y$$$, you get $$$A_i$$$ penalty
• If $$$S_i =\texttt{0}$$$ and $$$i \in Y$$$, you get $$$B_i$$$ penalty
• If $$$S_i = \texttt{1}$$$ and $$$S_j = \texttt{0}$$$ and $$$i \in X$$$ and $$$j \in Y$$$, you get $$$C_{i,j}$$$ penalty

In the below problems, we will work with the "natural" formulation of the problem and leave it to the reader to turn it into the proper min-cut version.

ABC259G

Here the indices are the set of rows and columns. We have $$$S_r = \texttt{1}$$$ if we chose row $$$r$$$ and $$$S_c = \texttt{1}$$$ if we chose column $$$c$$$.

Then the costs are as follows:

• If $$$S_r = \texttt{1}$$$, we pay $$$-\sum A_{r,i}$$$ penalty
• If $$$S_c = \texttt{1}$$$, we pay $$$-\sum A_{i,c}$$$ penalty
• If $$$S_r = \texttt{1}$$$ and $$$S_c = \texttt{1}$$$ and $$$A_{r,c} < 0$$$, we pay $$$\infty$$$ penalty
• If $$$S_r = \texttt{1}$$$ and $$$S_c = \texttt{1}$$$ and $$$A_{r,c} \geq 0$$$, we pay $$$A_{r,c}$$$ penalty

Then we simply set $$$X = {r}$$$ and $$$Y = {c}$$$ and all the constraints of type $$$C_{i,j}$$$ are between $$$X$$$ and $$$Y$$$.

ABC193F

We want to change this problem into one where we are minimising penalty so that $$$C_{i,j} \geq 0$$$. We will have penalty when two adjacent cells are the same color.

Denote $$$S_{(i,j)} = \texttt{1}$$$ if $$$(i,j)$$$ is colored black.

Then the costs are as follows:

• If $$$c_{i,j} = \texttt{B}$$$ and $$$S_{(i,j)} = \texttt{0}$$$, we pay $$$\infty$$$ penalty
• If $$$c_{i,j} = \texttt{W}$$$ and $$$S_{(i,j)} =\texttt{0}$$$, we pay $$$\infty$$$ penalty
• If $$$S_{(i,j)} = \texttt{1}$$$ and $$$S_{(i \pm 1,j \pm 1)} = \texttt{1}$$$, we pay $$$1$$$ penalty

Now, the trick is to realize that if we have $$$X$$$ and $$$Y$$$ contain all the cells $$$(i,j)$$$ where the parity of $$$i+j$$$ is $$$0$$$ and $$$1$$$ respectively, then all constraints of type $$$C_{i,j}$$$ are between $$$X$$$ and $$$Y$$$. This is corresponds to a chessboard coloring.

ARC142E

Let $$$c_i$$$ denote the final strength of the wizard. First, an obvious constraint is that for all pairs $$$(x,y)$$$, we have $$$c_x,c_y \geq \min(b_x,b_y)$$$. Let $$$mn_i$$$ denote the minimum value of $$$a_i$$$ under this constraint.

If the above constraint is true, the only other constraint we need to worry about is that $$$\max(c_x,c_y) \geq \max(b_x,b_y)$$$.

Now notice that $$$c_i$$$ and $$$b_i$$$ are small. For the indices of our binary string, it makes sense to define $$$S_{(i,v)} = \texttt{1}$$$ iff $$$c_i < v$$$.

Then the costs are as follows:

• If $$$S_{(i,v)} = \texttt{0}$$$ and $$$a_i \leq v$$$, we pay a penalty $$$1$$$
• If $$$S_{(i,v)} = \texttt{1}$$$ and $$$S_{(i,v+1)} = \texttt{0}$$$, we pay a penalty $$$\infty$$$
• If $$$(x,y)$$$ is a pair and $$$S_{x,\max(b_x,b_y)} = \texttt{1}$$$ and $$$S_{y,\max(b_x,b_y)} = \texttt{1}$$$, then we pay penalty $$$\infty$$$

Unfortunately, we find sets $$$X$$$ and $$$Y$$$ such that all constraints of the last type are between $$$X$$$ and $$$Y$$$ so easily this time. Luckily, we can delete some constraints by making some observations.

Let $$$X$$$ be the set of wizards such that for all pairs $$$(x,y)$$$, we have $$$b_y < b_x$$$. Let $$$Y$$$ be the other wizard. For all wizards in $$$Y$$$, we can deduce that $$$a_i \geq b_i$$$, since there exists some pair $$$(x,y)$$$ such that $$$b_x \geq b_y$$$ so that $$$a_y \geq \min(b_x,b_y) = b_y$$$.

Now, the extra constraint that $$$\max(a_x,a_y) \geq \max(b_x,b_y)$$$ ends up being needed only for pairs where one is in $$$X$$$ and the other is in $$$Y$$$. There are no pairs that are both in $$$X$$$. And all pairs in $$$Y$$$ automatically fufil our additional constraint.

Therefore, all troublesome constraints are between $$$X$$$ and $$$Y$$$ and we can use min cut here.