PROBLEM LINK:
Author: Maksym Bevza
Tester: Roman Furko
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Medium
PREREQUISITES:
Minimum cut, maximum flow, min-cut max-flow theorem
PROBLEM:
The floor of a plaza has dimensions N meters by M meters, and is split into R rooms. Walls separate different rooms.
There are two groups of engineers. For each room, there is a rent cost of C_1 for the first group and C_2 for the second group. Exactly one group of engineers must occupy each room. If two rooms that share a wall are occupied by different groups, then all shared walls must be made noise-resistant. The cost to make a meter of wall noise-resistant is K.
What is the minimum cost to occupy all rooms?
QUICK EXPLANATION:
Create a new graph with R+2 nodes, one for each room and two extra nodes Z_1 and Z_2. For every room, add an edge between Z_1 and that room with cost C_2, and between Z_2 and that room with cost C_1. For every two rooms that share W > 0 meters of wall, add an edge between them with cost WK. The answer is then the minimum Z_1-Z_2 cut.
Minimum cut can be reduced to maximum flow using the min-cut max-flow theorem, and there are many standard ways to solve max flow problems. For this problem, we can use the Edmonds-Karp algorithm which runs in O(VE^2) time. In our case, this reduces to O(R^3).
EXPLANATION:
If we didn’t care about adjacent rooms, then the following simple greedy strategy is correct: place in each room the engineer group with a lower rent. However, obviously this isn’t enough for the actual problem, because placing different groups on two adjacent rooms also cost something (depending on the amount of wall they share). This complicates things a bit. To solve the problem, we must find the right balance of minimizing the rents and the penalties of placing different groups on adjacent rooms.
Let’s draw a new graph with R nodes, one for each room. Also, let’s add an edge between every two adjacent rooms, setting its weight to be the total cost of making all walls between them noise-resistant (i.e. if the rooms share W meters of wall, the weight is WK). Then to get the answer, we want to cut this graph into two groups of nodes so that the total weight of edges connecting nodes from different groups plus the rents is minimized. Some may recognize similarities with the minimum cut problem, a standard problem with many known efficient solutions. There are slight differences with minimum cut, though, because:
- There are no “source” and “sink” nodes.
- We also need to take into account the rents.
But thankfully, these two problems can be solved simultaneously by adding two new nodes, which we’ll call Z_1 and Z_2. For every room, we add an edge between Z_1 and that room with cost C_2, and between Z_2 and that room with cost C_1. This way, the answer is then simply the minimum Z_1-Z_2 cut! The idea is that making a Z_1-Z_2 cut makes every “room node” reachable from exactly one of Z_1 or Z_2. We interpret this as having the first or second group occupy that room, respectively. Notice that:
- Making a room reachable from Z_1 forces us to cut the edge connecting it to Z_2. Similarly, making a room reachable from Z_2 forces us to cut the edge connecting it to Z_1. This corresponds to “paying the rent” in the original problem.
- Making a room reachable from Z_1 and an adjacent room reachable from Z_2 forces us to cut the edge between them, and this corresponds to “making the walls between them noise-resistant” in the original problem.
Thus, assignments of rooms correspond to Z_1-Z_2 cuts! (If you want to rigorously show why this is correct, you need to show that any assignments of rooms to the two groups determines a Z_1-Z_2 cut whose weight is equal to the cost of the assignment, and vice versa. This is simple and straightforward as long as you know the correspondence between a cut and the assignment of rooms.)
Here’s an example. The following image illustrates the graph obtained from the sample input.
The minimum cut between Z_1 and Z_2 is clearly 48:
This says that rooms 2 and 3 must be assigned the first group, and room 1 assigned the second group.
Finding the minimum cut
Finding the minimum cut is a standard problem, and the usual way of doing it is by reducing it to the maximum flow problem via the min-cut max-flow theorem. Now, there are many standard ways to solve max flow problems. Usually, the faster ones are harder to implement. For this problem, I recommend the Edmonds-Karp algorithm, which runs in O(VE^2) time, where V and E is the number of vertices and edges, respectively. The time complexity seems bad, because in a general graph the worst case complexity of E is O(V^2), so the complexity seems to be O(V^5) which is too slow. However, in our case this doesn’t happen because E is a lot smaller than V^2. To see this, suppose we remove the nodes Z_1 and Z_2. Then we remove 2(V-2) edges along with them. But after doing so, we are left with a graph of R nodes whose edges are determined from walls being shared in a rectangular room. This means that our graph with Z_1 and Z_2 removed is a planar graph, and in such graphs we know that E' \le 3V' - 6 (whenever V' \ge 3). Thus, our original graph has at most 5V nodes, so E = O(V) = O(R) and the time complexity of Edmonds-Karp becomes O(R^3) 
(In practice this could even be a lot faster because worst case scenarios for max-flow algorithms tend to come up rarely.)
A minor optimization: For every room i, instead of adding the edges (Z_1,i) and (Z_2,i) with costs C_2 and C_1, we can instead add only one of them. Specifically, we only add the edge with the larger cost and replace the cost with \left|C_1 - C_2\right|, and then just add \min(C_1,C_2) to the answer at the end. This works because each room will be occupied by one group anyway, so we will definitely incur a cost of at least \min(C_1,C_2) for each room, but we will incur an additional \left|C_1 - C_2\right| if we choose to place the group with the higher rent in that room. Thus, the answer remains the same. But this optimization reduces the number of edges in our graph by R and saves you at least O(R) iterations of the Edmonds-Karp algorithm, so some amount of computation might be saved. (The time complexity remains O(R^3) though.) This optimization is implemented in my (editorialist’s) solution. You can check the code below.
Time Complexity:
O(NM + W + R^3)
