Task Information for Traffic Congestion
Task Author: Jorge Bernadas (VEN)
This was (by intention) a fairly standard task.
Though, it should be mentioned that graph problems always are a bit
trickier than one might at first think because of the need to handle
specific graph encodings.
The information provided below will be expanded in the future,
but for now should help in understanding what each subtask
was expecting in the form of algorithms.
- Subtask 1: Quadratic works.
Because of the highly regular (linear) structure of the network graph,
it is easy to try each city as location for the arena, calculate
the worst congestions and pick out the location where this worst
congestion is minimal.
- Subtask 2: Requires linear algorithm,
but because there are only two leaves and the graph representation
is highly regular, it is easy to see that one sweep over the
cities along the roads suffices to determine the optimum location.
- Subtask 3: Quadratic works,
but now the general graph must be handled.
Again, as in Subtask 1, every city can be tried as arena location,
the worst congestion can then be calculated, and best location can
- Subtask 4: This is the full problem.
A linear traversal of the graph, accumulating congestion information
appropriately, enables one to determine the optimal location of the arena
in linear time.