12287 - Network Flow
Moderator: Board moderators
-
brianfry713
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
12287 - Network Flow
Use this thread to discuss this problem.
Check input and AC output for thousands of problems on uDebug!
Re: 12287 - Network Flow
It seems to me there's something wrong with the data for this problem.
Ignoring the part about optimizing the rotation in the flow, I'm having difficulty understanding how to justify the TRA computation used to get ACC (which I just got).
Consider the following cases, which all specify the same pump and are all simple polygons (so, there isn't any choice how to route the water, except for which direction to send it which doesn't affect TRA).
8 1 1 1 1 1
2 0 3 0
3 0 4 1
4 1 4 2
4 2 3 3
3 3 2 3
2 3 1 2
1 2 1 1
1 1 2 0
4 1 1 1 1 1
0 0 1 0
1 0 1 1
1 1 0 1
0 1 0 0
3 1 1 1 1 1
0 0 1 1
1 1 1 0
1 0 0 0
0
ACC solution gives
Case 1: 75.00
Case 2: 75.00
Case 3: 87.50
So, the octagon & square have the same TRA, which makes sense under one interpretation of TRA, because overall the "velocity vector" of the water goes through exactly one rotation, and whether it goes through eight vertices or four doesn't really change that.
However, under that interpretation (which I'd argue is the natural one based on the "story" in the problem statement), it should be the same TRA for the triangle as well.
Meanwhile, if one interprets the problem statement *literally*, it says "After the flow is complete, a polygon is created by tracing the path of water flow inside the network. Then at each node of the polygon, we take the smallest angle between the two lines adjacent to it." This is a weird definition (ignores how water flowing through this vertex would actually need to be pumped) but would give 87.50 for the triangle. However following the same idea for octagon would give 25.00.
In order to get ACC, I had to take the smaller of the two options at each vertex (and then solve the rest of the problem dealing with how to minimize TRA in more complicated graphs). I suppose one can justify that by interpreting "lines" in the above quoted part of the statement as meaning actual infinite lines (instead of the lines that we have "traced" by following the water's path), and so at each vertex of the polygon we take the smaller of either interior or exterior angle. I feel that this is a major stretch since it makes no sense in the context of the pump needing to change the water flow's direction.
As far as I'm concerned, this problem should actually be about exterior angle sum since that's what corresponds to the work a pump would have to do. A secondary issue with the data seems to be how the final answer is calculated (the statement speaks in terms of energy 'e' but actually the output is the unused available TRA). That one is less of a problem because the sample input clears it up well enough, but it is peculiar since if one doesn't need to backsolve for 'e' then it doesn't really make sense why the pump is specified using a polynomial.
Ignoring the part about optimizing the rotation in the flow, I'm having difficulty understanding how to justify the TRA computation used to get ACC (which I just got).
Consider the following cases, which all specify the same pump and are all simple polygons (so, there isn't any choice how to route the water, except for which direction to send it which doesn't affect TRA).
8 1 1 1 1 1
2 0 3 0
3 0 4 1
4 1 4 2
4 2 3 3
3 3 2 3
2 3 1 2
1 2 1 1
1 1 2 0
4 1 1 1 1 1
0 0 1 0
1 0 1 1
1 1 0 1
0 1 0 0
3 1 1 1 1 1
0 0 1 1
1 1 1 0
1 0 0 0
0
ACC solution gives
Case 1: 75.00
Case 2: 75.00
Case 3: 87.50
So, the octagon & square have the same TRA, which makes sense under one interpretation of TRA, because overall the "velocity vector" of the water goes through exactly one rotation, and whether it goes through eight vertices or four doesn't really change that.
However, under that interpretation (which I'd argue is the natural one based on the "story" in the problem statement), it should be the same TRA for the triangle as well.
Meanwhile, if one interprets the problem statement *literally*, it says "After the flow is complete, a polygon is created by tracing the path of water flow inside the network. Then at each node of the polygon, we take the smallest angle between the two lines adjacent to it." This is a weird definition (ignores how water flowing through this vertex would actually need to be pumped) but would give 87.50 for the triangle. However following the same idea for octagon would give 25.00.
In order to get ACC, I had to take the smaller of the two options at each vertex (and then solve the rest of the problem dealing with how to minimize TRA in more complicated graphs). I suppose one can justify that by interpreting "lines" in the above quoted part of the statement as meaning actual infinite lines (instead of the lines that we have "traced" by following the water's path), and so at each vertex of the polygon we take the smaller of either interior or exterior angle. I feel that this is a major stretch since it makes no sense in the context of the pump needing to change the water flow's direction.
As far as I'm concerned, this problem should actually be about exterior angle sum since that's what corresponds to the work a pump would have to do. A secondary issue with the data seems to be how the final answer is calculated (the statement speaks in terms of energy 'e' but actually the output is the unused available TRA). That one is less of a problem because the sample input clears it up well enough, but it is peculiar since if one doesn't need to backsolve for 'e' then it doesn't really make sense why the pump is specified using a polynomial.