Consider the town as a grid $N$ x $N$. Thus, there are $(N+1)(N+1)$ of junctions and $2N(N+1)$ two-way roads. Every intersection has a height. It is known that the upper left intersection has a height of $0$, and the lower right the height $1$. For each road we know how many people go in each direction on this road. In this case, if the road leads from the intersection $i$ to the intersection $j$ and the height difference $h = h_j - h_i$, the inconvenience of moving every person on this road is equal to $\max(h, 0)$. For all intersections except two angle are allowed to choose any height. It is necessary to minimize the total inconvenience. In the end, it is necessary to obtain only a total inconvenience, the individual heights are not needed.

I think all heights will lie in the set $\{0, 1\}$. It is clear that you can honestly cycle through all the bitmaps and choose the best. But you need to find more efficient algorithm. One of my ideas was to put all the intersections in the upper left part of the height equals $0$, and the right lower part of the height equal to $1$. Here would be required to find the optimal boundary. I came up with a way of solving by finding maximum flow of minimum cost in $O(N^8)$. Can it be better?


enter image description here

P. S. Sorry for my bad English.

  • $\begingroup$ 1. What does "angle are allowed to choose any height" mean? I'm confused by what the word "angle" means here. 2. Do you know of any proof that all the heights will be in {0,1} for the optimal solution? 3. How did you solve this in $O(n^8)$ time with max flow? 4. Have you tried expressing the problem as a graph cut problem? 5. Please choose a more descriptive title. $\endgroup$ – D.W. Jun 14 '16 at 5:54

This problem is exactly the problem of finding the minimum $(s,t)$ cut in a directed graph, where $s$ is the upper-left corner and $t$ is the lower-right corner. All the vertices on the $s$ side of the cut will be assigned height 0; all the vertices on the $t$ side of the cut will be assigned height 1; and the capacity of the cut is equal to the sum of the counts on the edges that cross the cut in the $s\to t$ direction. You want to minimize this sum, so you want to find the minimum $(s,t)$ cut. There are many standard algorithms for doing that, based on finding a maximum flow and then applying the min-cut max-flow theorem.

  • $\begingroup$ What is the complexity of the algorithm can be achieved? $\endgroup$ – Linkin Jun 14 '16 at 6:32
  • $\begingroup$ @Linkin, pick any max-flow algorithm. They're well-documented - see, e.g., Wikipedia. $\endgroup$ – D.W. Jun 14 '16 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.