Problem: http://code.google.com/codejam/contest/311101/dashboard#s=p3&a=3
Official Explanation: http://code.google.com/codejam/contest/311101/dashboard#s=a&a=3 In official explanation, it says: To reduce the problem to an instance of MIN-CUT, we create a flow network as follows. Create a source vertex, a sink vertex, and one vertex for each tower. Suppose a tower has score s. If s > 0, create an edge from the vertex to the sink with capacity s. If s < 0, create an edge from the source to this vertex with capacity |s|. Finally, for every edge in the connection graph, create a similar edge in the flow network with infinite capacity. Does the last sentence (... similar edge ...) means "If a tower A has another tower B in its range, we represent this fact as a directed edge from A to B."? It seems that the sample input will form a zero-flow graph. Or the last sentence (... similar edge ...) means "If a tower A has another tower B in its range, we represent this fact as a directed edge from B to A."? It seems that the sample input will form a meaningful graph. But this is not what official explanation said in the "Connection graph" section. Does anyone else feel that the pharse "similar edge" is quite ambiguous? What's the true meaning of "similar edge"? -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
