PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
Problems which ask to block all possible paths usually have something to do with cuts in a graph. This problem is no exception, we just need to set up the right model. Lets begin with some observations:
- Raising cell A possibly results in new outgoing edges from A and blocks some incoming edges.
- If in an optimal solution cell A is raised, then there is no valid path from the restaurant to A.
If such path existed, we might as well leave A at its initial height - possibly reducing the number of outgoing and increasing the number of incoming edges. Reducing the number of outgoing edges can only improve the solution and if we already have an incoming path, adding some new incoming edges won’t change anything. Note that no path from A to town exists or the solution wouldn’t be valid.
- The height of every raised cell in an optimal solution will be equal to 1 + initial height of one of its neighbours.
It is obvious that the final height of any raised cell will be 1 + final height of one of its neighbours. But why can we make that claim with initial instead of final heights? Lets say we have two neighbouring raised cells A and B with h(B)=h(A)+1, where h(X) denotes final height of cell X. There is no need to raise cell B over A if there is no path from restaurant R to cell A, which follows from observation2.
We can model each cell with a linked list of 5 nodes. Last in the list is the outgoing node and the other four represent incoming nodes from neighbouring cells sorted by their height. Numbers next to nodes represent initial elevations of cells. Cutting an edge with cost x corresponds to raising the cell by x. All that’s left is finding minium cut in this graph, which is equal to maximum flow by max-flow min-cut theorem.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.