15295 Spring 2022 #9 Network Flows -- Problem Discussion
March 23, 2022
This is where we collectively describe algorithms for these problems. To see the problem statements and scoreboard, go to this page and select this contest.
A. Soldier and Traveling
See this page.
B. Bart's Beeers
Adapt the solution of “Amy Tiles” from this recitation to this problem.
C. Ciel and Duel
D. The Doctor Meets Vader (Medium)
E. The Doctor Meets Vader (Hard)
Finished this problem a few minutes late after the contest ended…
Notice that this problem is completely different from D, since each base can be attacked by multiple ships, so we can just precompute the best base for each ship and always let it attack that base. Naively, precomputing this takes O(sb) time, which is too large in this case since s and b can be 1e5 in this problem. Notice that n is small, we can break the bases into n groups based on the vertex it is on. For each group, we sort the bases based on the defense in decreasing order, and compute the largest gold for every suffix. Then, for every ship, we iterate through the n groups, and binary search on the defense. Then, the maximum gold will be the precomputed maximum suffix gold of the result of binary search. This takes time at most O(sn log b).
Then, we consider how to solve the dependencies. We see that after we compute the maximum gold for each ship, the gain for that ship to attack can be either positive or negative. Without dependencies, the ship would attack if the gain is positive and not if the gain is negative. Since s can be as large as 1e5 but the number of dependencies is at most 1e4, we can first process the ships without dependencies. Then, for the ships with dependencies, we can solve this problem using min-cut. We build a flow network as follows. Each ship is a node, and there is a directed edge for every dependency with infinite capacity. If the gain for the ship is positive, then we add an edge from the source to the node with capacity equal to the gain. If the gain for the ship is negative, then we add an edge from the node to the sink with capacity equal to the absolute value of the gain. Then, consider how we could find a cut in this network. For each dependency (i, j), at least one must hold: either we don’t attack i or we attack j. Similarly, we must cut (s, i) or (j, t). Then, if we interpret (s, i) in the cut as “don’t attack i” and (j, t) in the cut as “attack j”, a cut is equivalent to an valid solution to the problem. The value of the min-cut is min (sum positive gain that don’t attack) - (sum negative gain that attack), where the minus sign is because we take the absolute value. If we calculate (sum positive gain), and minus the value of the min-cut, we get max (sum positive gain that attack) + (sum negative gain that attack), which is the result we want. Time complexity is O(k^3) and faster in practice if you use Dinic’s algorithm.
There was a programming hw in 15-451 last semester that is very similar to the second part of this problem using min-cut: https://www.cs.cmu.edu/~15451-f21/hws/hw4.pdf
– Yan
F. Bricks
The key is to invert the problem: instead of starting from an empty board and adding blocks, start with every place being a block of its own, and then merging adjacent blocks. Of course, every time you merge two adjacent blocks, the total number of blocks used reduces by 1. And so the goal is to merge as many blocks as possible.
For any two adjacent blocks, consider the edge between them. Merging these two blocks is equivalent to selecting this edge, and so we want to select as many edges as possible. Then, notice that the only case in which merges are invalid is if you merge two edges which are 90 degrees apart, and share a common block. For clarity I’ll now refer to these edges as sides. Make a node for each side. Then, make an edge between any pair of sides which cannot be selected together. Then, since we’d like to select as many nodes as possible, we need to find the maximum independent set (MIS) of this graph.
Fortunately, the graph is bipartite (horizontal sides are connected only to vertical sides, you cannot draw edges between horizontal and horizontal or vertical and vertical edges). So we can run a max cardinality bipartite matching on this graph using augmenting paths. There’s some theorem which states that the MCBM = MVC (min vertex cover), so this value is equal to the MVC. Then, the MIS is the complement of the MVC. So now we have the MIS. We subtract this from the total number of positions needing to be covered for our final answer.
G. Making It Bipartite