Editorial for COCI '13 Contest 6 #6 Graškrižja
Submitting an official solution before solving the problem yourself is a bannable offence.
Let us sort the given traffic lights by their -coordinate. Let
be the middle (median)
-coordinate in that array. Let
be a set of given traffic lights to the left of
and
to the right.
We will construct a harmless path between each pair of traffic lights ,
such that
is from the set
and
is from the set
. How? By adding new traffic lights to the locations
for each
-coordinate
from the sets
and
. Now for traffic lights
and
we have a harmless way
.
Now all we need to do is connect the traffic lights within the set with one another, as well as those within the set
. We do this by recursively repeating the described procedure, specifically for set
and specifically for set
. This way of thinking is called divide and conquer.
A little bit of thinking is needed to be sure that the new traffic lights don't generate any new dangerous paths, but the implementation is reasonably simple.
What is the number of additional traffic lights? Given the fact that we divide the set into two parts, the maximal depth of recursion is . Let us observe an initial traffic light at the location
. Worst case scenario, at every depth of the recursion, it will be included in a set and there it will generate a new traffic light
. Therefore, one initial traffic light generates
new traffic lights, which gives us a total of
new traffic lights. With careful implementation, the exact number turns out to be less than
.
Comments