Thanks a lot, I get it now.
On 06/02/2014 12:27 PM, Luke Pebody wrote:
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]
<mailto:[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]
<mailto:google-code%[email protected]>.
To post to this group, send email to [email protected]
<mailto:[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]
<mailto:[email protected]>.
To post to this group, send email to [email protected]
<mailto:[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
<https://groups.google.com/d/msgid/google-code/CAECKw-P-ed%2B-ADKAUwRGZAaD0V1tEpWt-ku6zuopUx%2Bz2AUw4g%40mail.gmail.com?utm_medium=email&utm_source=footer>.
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/538DD186.5030605%40mailbolt.com.
For more options, visit https://groups.google.com/d/optout.
