J. Son of Pipe Stream
event sponsor ICPC 2017 Problem J Son of Pipe Stream Time limit: 5 seconds Two years ago, you helped install the nation’s very first Flubber pipe network in your hometown, to great success. Polls show that everyone loves having their own Flubber dispenser i...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
Two years ago, you helped install the nation’s very first Flubber pipe network in your hometown, to great success. Polls show that everyone loves having their own Flubber dispenser in their kitchen, and now a few enterprising citizens have discovered a use for it. Apparently Flubber, when mixed with water, can help extinguish fires! This is a very timely discovery, as out-of-control fires have lately been surprisingly common. Your hometown’s city council would like to make use of this property of Flubber by creating the Flubber/wa- ter mixture at a centrally located station. This station, which is called the Flubber Department (FD) will also have specialized employees trained to travel to the locations of fires and make use of their processed Flubber to control the blazes. The pipes are already in place all around the city. You are given a layout of the pipes, and must determine how to route Flubber from the Flubber factory and water from a local source through the pipes to the FD. Note that both Flubber and water will be flowing through the same network of pipes, perhaps even the same pipe. All pipes are bidirectional, but Flubber and water cannot move in opposite directions through the same pipe. Furthermore, if both liquids are sent in the same direction through the same pipe, they will inevitably mix. Therefore the nodes in the network have been equipped with special membranes and filters that enable you to separate and reorganize all incoming mixtures as you see fit. The network is a closed system, so the total rate of each fluid going into a node must equal the total rate of that fluid going out, except at the source of that fluid and the destination (the FD). Each pipe has a certain capacity. Flubber, being somewhat sluggish, has a viscosity value v, so a pipe that can transport v liters/second of water can transport only 1 liter/second of Flubber. The pipe’s capacity scales linearly for mixtures of the two. To be precise, if c denotes the water capacity of the pipe and f and w are the rates of Flubber and water moving through the pipe (all measured in liters/second), then the capacity constraint is given by the inequality v · f + w ≤ c. Your main concern is balancing the mixture that reaches the FD. You would like as much total liquid as possible, but you also need a sufficient amount of water – because undiluted Flubber is highly flammable – and a sufficient amount of Flubber – because it would not be much of a “Flubber Department” without Flubber! You have come up with a formula to measure the “value” of the final mixture: F a · W 1−a , where F is the rate of incoming Flubber in liters/second, W is the rate of incoming water in liters/second, and a is a given constant between 0 and 1. Determine the maximum value of F a · W 1−a that can be achieved and how to route the Flubber and water to achieve it.
Input
The input starts with a line containing the number of locations n (3 ≤ n ≤ 200), the number of pipes p (n − 1 ≤ p ≤ 12 n(n − 1)), and the real values v (1 ≤ v ≤ 10) and a (0.01 ≤ a ≤ 0.99). Locations are numbered from 1 to n; 1 is the Flubber factory, 2 is the water source, and 3 is the FD. The real values have at most 10 digits after the decimal point.
Rapid Citysponsor
ICPC 2017The following p lines each describe one pipe. Each line contains two integers j and k (1 ≤ j < k ≤ n), giving the locations connected by the pipe, and an integer c (1 ≤ c ≤ 10), giving the water capacity of the pipe in liters/second. No two pipes connect the same pair of locations. Furthermore, it is guaranteed that the network is connected.
Output
First, for each pipe (in the order given in the input), display two values: the rate of Flubber moving through it, and the rate of water moving through it (negative if the liquid is moving from k to j), such that F a · W 1−a is maximized. Then display that maximum value accurate to within an absolute error of 10−4 . If there are multiple solutions, any one will be accepted. All constraints (not sending Flubber and water in opposite directions along the same pipe, flow conservation, pipe capacities, and consistency between the constructed solution and its claimed value) must be satisfied within an absolute error of 10−4 .
Sample Tests
6 6 3.0 0.66
2 4 8
4 6 1
3 6 1
4 5 5
1 5 7
3 5 30.000000000 1.360000000
0.000000000 1.000000000
0.000000000 -1.000000000
0.000000000 0.360000000
0.880000000 0.000000000
-0.880000000 -0.360000000
1.02037965897 5 5 1.0 0.5
1 2 10
2 3 10
3 4 10
4 5 10
3 5 105 0
5 5
4.2 3.14159
4.2 3.14159
-4.2 -3.14159
5Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observations
Write the structural observations that make the problem tractable.
State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
If the constraints matter, explain exactly which part of the solution they enable.
Algorithm
Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
Mention corner cases explicitly if they affect the implementation.
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
State the first key claim.
Proof.
Provide a concise proof.
Lemma 2.
State the next claim if needed.
Proof.
Provide a concise proof.
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
Combine the lemmas and finish the argument.
Complexity Analysis
State the running time and memory usage in terms of the input size.
Implementation Notes
Mention any non-obvious implementation detail that is easy to get wrong.
Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2017/J-son-of-pipe-stream/solution.texC++ implementationcompetitive_programming/icpc/2017/J-son-of-pipe-stream/solution.cppStatement textcompetitive_programming/icpc/2017/J-son-of-pipe-stream/statement.txtStatement PDFcompetitive_programming/icpc/2017/J-son-of-pipe-stream/statement.pdfMetadatacompetitive_programming/icpc/2017/J-son-of-pipe-stream/meta.jsonYear packetcompetitive_programming/icpc/2017/contest_problems.pdf