On Monday, June 2, 2014 4:31:21 PM UTC+2, Matt 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.
Solving a max-flow problem is the same as finding a min-cut, which in this case amounts to finding a shortest path from the West to the East, with the buildings as nodes and the rivers as edges. The number of buildings is reasonable enough to permit this. -- 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/7dabc644-361b-4ef5-8e3d-bc508884c715%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
