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 be found.

• 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.