Editorial for Wesley's Anger Contest 4 Problem 6 - Hungry Squirrels


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: wleung_bvg

Subtask 1

For the first subtask, we can think of the movement of acorns as a flow network. We can create edges from the source node to each of the nodes representing the M trees with a capacity equal to f_j. We can then add edges from each of the nodes representing the N squirrels to the sink node with a capacity equal to b_i. Finally, we can add edges from the j^{th} tree to the i^{th} squirrel with a capacity equal to d_{ij}. We can run a maximum flow algorithm on the graph to determine the maximum acorns that need to be collected. The minimum is always 0. The squirrels will always survive the quarantine without wasting food if 0 acorns are produced and consumed.

Time Complexity: \mathcal{O}((N + M)^3) if the Push-Relabel algorithm is used, though efficient Dinic and Edmonds Karp implementations should both pass within the time limit.

Subtask 2

For the second subtask, we can think of a_i, c_{ij}, and e_j as minimum demands for the edges in the flow network. While there are methods to handle the demands for this specific structure of the graph, we can also use a more general method by first finding any feasible flow. First, we can create a new flow network with a new source and sink. We add an edge from the new source to every vertex in the original graph with a capacity equal to the sum of demands of all outgoing edges from that vertex in the old graph. We add an edge from each vertex to the new sink with a capacity equal to the sum of the demands of all incoming edges to that vertex in the old graph. We add an edge between each pair of vertices where there existed an edge between that pair in the old graph, with a capacity equal to the demand subtracted from the old capacity. Finally, an edge is added from the old sink to the old source with an infinite capacity. After running the maximum flow on the new graph, we can determine if there is a feasible flow in the old graph by determining if every outgoing edge from the new source has a residual capacity of 0. The value of the feasible flow can be found by looking at the flow on the edge from the old sink to the new source.

To determine the max flow, we can run the maximum flow algorithm on the residual graph after finding the feasible flow (using only the original edges) and adjusting the edges for the subtracted demand. Remember to add the value of the feasible flow.

To find the minimum flow, we can observe that if we lower the capacity of the edge from the old sink to the new source, eventually, there will be no feasible solution. We can binary search for the value of this edge in order to determine the minimum capacity of this edge, where a feasible flow exists, which is also equal to the value of the minimum flow.

Let K = \sum_{1}^N b_i

Time Complexity: \mathcal{O}((N + M)^3 \cdot \log{K}) if the Push-Relabel algorithm is used, though an efficient Dinic implementation should pass within the time limit.


Comments


  • 15
    ecnerwal  commented on April 29, 2020, 3:30 p.m.

    You don't need any binary search for the minimum flow. Assume there is some feasible flow. Then just delete the entire edge from the old sink to the new source, and compute the max-flow in this graph. The minimum flow will be exactly the total demands minus this flow, as we know a feasible flow exists, so any extra desired demand must go through the sink->source edge.