Dear all,
I am having trouble understanding the solution to this problem on Kattis. I hope someone can help me explain the solution.
Summary of the problem: Given a 2D binary table, each ceil is either high or low. The cost go from a low ceil to a high one is A, the cost to "low down a high ceil" is B. We must find the minimum total cost of traveling through all columns and then all rows by lowing down some ceils?
Summary of the solution: Create a graph with n * m (ceils in the table) + 2 (source and sink) vertexes, connect the source to all low ceils and connect all high ceils to the sink with edges having capacity of B, connect ceils to their neighbors (regardless of the heights) with edges having capacity of A. The answer is the min cut max flow from source to sink.
I try my best but still unable to understand the meaning of this solution. I think this is a great application problem of max flow min cut, so I hope someone can help me.
Thank you so much for your time and consideration.
Reformulation of the statement which I like much more: "each cell is either in set I or set II; you can move cell from one set to another for B; you have to pay A for each pair of adjacent cells which are in different sets in the end; minimize your costs".
I feel that it's much more useful to think about max-flow problems in terms of min-cut (see max-flow min-cut theorem). Min-cut is essentially the following: you have a graph with two selected nodes (source and sink) and you have to arrange its nodes in sets I and II such that:
If I listed something new for you above, I recommend stopping here and trying to figure out the solution yourself.
Basically, the idea of the solution now is to construct a right graph. In that case, vertexes are quite straightforward: cells + source + sink. Paying for adjacent cells is also straightforward: add edge between all adjacent cells of weight A. Paying for changing cell's height is what we need source+sink for: if the cell is initially in set I, we add edge from the source to it of weight B (i.e. if that cell is moved to set II, we pay B). Similarly, if the cell is initially in set II, we add edge from it to the sink of weight B (if that cell moves to set I, we pay B).
Now, you just find min cut with any max-flow algorithm. I have no idea how to interpret that flow. Just look at the min cut.
Thank you. I have somehow figured out the picture. In the constructed graph, instead of connecting every ceil to its neighbors, we can connect two ceils if they have different heights only. That makes things clearer for me because at the beginning, I could not understand why we need no connect two ceils if they have the same heights. The funny thing is it works either way.
I don't think that connecting two cells if they have different heights only leads to the correct solution. It may be the case, but it has to be proven separately; it's not obvious to me right away.
The idea of connecting every two neighbors is because we pay for any pair of neighbors as long as they will have different height in the answer. Having an edge between two cells is like saying "if they eventually end up of different heights, we pay this; if they're on the same height, pay nothing".
Another way of telling the same: we have to somehow tell the graph that these cells are "neighbors", just in case it would want to change heights of some of them only. If you don't connect neighboring cells of the same height, the graph wouldn't contain any information that they're neighbors and max flow can produce some obscure solution which would exploit the fact that they're not considered "neighbords".