← All solutions

Solved by 0 teams.

Shortest judge solution: 1612 bytes.

We can clearly express this problem as a linear program, with a variable for the amount of flow entering each duct, and a variable for a lower bound on the fill rate of any reservoir; we want to maximize the latter. Each station provides an equality (flubber in equals flubber out), but for simplicity we can write it as an inequality (flubber in ≥ flubber out), since discarding flubber will not increase the answer.

The strong duality theorem of linear programming tells us that we can instead compute the answer for the dual problem. The dual can be expressed as follows. Associate a nonnegative score w with each station and reservoir. The sum of w over the reservoirs must be at least 1. For every duct, the score of the upstream station must be at least the sum of those of the downstream stations/reservoirs scaled by the drainage factions (p). The objective is to minimize the w of station 1.

There are some obvious simplifying assumptions. Firstly, the w values for the reservoirs will sum to exactly 1 (otherwise all w values can be scaled down to improve the objective). Secondly, the w value for any station will be the maximum of the lower bounds implied by any of the ducts. Thus, once we’ve chosen r − 1 of the reservoir w’s, we can sweep backwards to compute the optimal objective.

If r = 2, we just need to optimize a single w value. Since linear programming leads to convex functions, we can use ternary search to find the optimum. For r = 3 we can use a nested ternary search: with w₁ fixed, use ternary search to optimize w₂; and then use this as a black box to optimize w₁ with another ternary search.