I didn't work it out during the round, but my solution involves using the Maximum Flow - Minimum Cut theorem to say that the maximum flow is equal to the number of vertices you need to remove for no flow to be possible.
Now any set of vertices that cut off all flow will start at the left edge, then move through some number (possibly 0) of buildings and end up at the right edge. The number of squares needed to get from building 1 from (top1, left1, bottom1, right1) to (top2, left2, bottom2, right) is max(top1-1-bottom2,top2-1-bottom1,left1-1-right2,left2-1-right1). So: add 2 new buildings, the first representing the left edge at (0,-1,height-1,-1) and the second representing the right edge at (0,width,height-1,width), and find the shortest path from the left building to the right building using the above metric. You could use Djikstra's Algorithm The code I wrote that solves it (using my Python code jam wrapper that can be found at http://jamftw.blogspot.co.uk/2012/05/python-code-jam-wrapper.html) is: def reader(inFile): (w,h,b) = inFile.getInts() boxes = [((x0,y0),(x1,y1)) for i in xrange(b) for [x0,y0,x1,y1] in [inFile.getInts()]] return (w, h, boxes) from fractions import gcd def distance(((x0,y0),(x1,y1)),((x2,y2),(x3,y3))): return max(x2-x1-1,x0-x3-1,y2-y1-1,y0-y3-1) def solver((w, h, boxes)): if len(boxes) == 0: return w n = len(boxes) dists = [x0 for ((x0,y0),(x1,y1)) in boxes] stilltodo = set(range(n)) for i in xrange(n): (dist, closest) = min([(dists[i],i) for i in stilltodo]) stilltodo.remove(closest) for k in stilltodo: dists[k] = min(dists[k], dist + distance(boxes[k], boxes[closest])) return min([dists[i] + (w - 1 - boxes[i][1][0]) for i in xrange(n)]) if __name__ == "__main__": from GCJ import GCJ GCJ(reader, solver, "/Users/luke/gcj/2014/2/c/", "c").run() On Mon, Jun 2, 2014 at 3:30 PM, Matt Weaver <[email protected]> wrote: > I really enjoyed the problem set for round 2. I still haven't figured out > the solution for problem C though, Don't Break the Nile. Can anyone give > me the short version while we wait for the analysis? I can see how it could > be modeled as a maximum flow problem, but it would be way too large to be > solvable. I assume from the large constraints it should be possible to > process row-by-row up the river, but any method I can think of breaks down > on maze-like rivers with dead ends, etc. where it seems like you would need > to backtrack. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit https://groups.google.com/d/ > msgid/google-code/538C8A99.4060400%40mailbolt.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-P-ed%2B-ADKAUwRGZAaD0V1tEpWt-ku6zuopUx%2Bz2AUw4g%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
