PROBLEM LINKSDIFFICULTYHARD EXPLANATIONProblems 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:
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.
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. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 26 Nov '12, 19:55
