Editorial for WC '15 Contest 3 S4 - Lex Luthor's Landmines
Submitting an official solution before solving the problem yourself is a bannable offence.
For starters, let's sort the landmines in non-decreasing order of position. This takes time. Our primary goal will be to compute the values
and
for each mine
– the minimum and maximum positions that will be engulfed in an explosion if mine
is set off. From here, one naïve thing to try would be a straightforward simulation using breadth-first search. To compute the
and
of each initial mine, we can add it to the queue. Processing each mine as we pop them from the queue, we can loop through all other mines to see if that mine is set off. The simulation for each mine will take
. For
mines, that is
overall. To finally process each query position
, we can naively loop through all of the mines and count the number of mines that have
and
ranges including
. Since there are at
queries, the running time for this part is
. This solution is given 15/40 of the points.
We can try certain optimizations such as gradually expanding the explosion range for each initial mine. This will get each simulation from to
, yielding
across all
mines. However, that is still too slow for
as large as
. Furthermore, answering queries also happens to be a bottleneck, with
up to
. We will need to speed up both sections to sub-quadratic running time to pass under the time limit.
For a full solution, we can start by representing the mines as the nodes of a directed, unweighted graph. Let there be an edge from mine to mine
if mine
's explosion would directly set off mine
(in other words, if
). The purpose of this graph is that
and
can be computed based on the
and
values of mines which have edges leading into mine
(for example,
is equal to the minimum of
and the
values of those mines).
One issue with this graph is that it can have edges. However, the observation can be made that keeping at most two incoming edges for each mine
will suffice – the edge leading from the mine whose position is in the interval
which has the minimum
value, and similarly the one which has the maximum
value. These (at most) two mines are clearly at least as important as any other mines that mine
can directly set off. Both of the mines can be found in
time by using a segment tree to perform a range minimum/maximum query on the
/
values of the mines.
We now have a graph with edges which represent the relationships between the mines'
and
values, but it doesn't yet give us an appropriate order in which to compute these values based on one another, due to the fact that it can have cycles. If two mines are reachable from one another in this graph, they must have the same
and
values. As such, the next step is to locate all of the strongly connected components in the graph (in
time using an algorithm such as Tarjan's). Each strongly connected component can then be contracted to a single node, which stores the number of actual mines in the node as well as their minimum
value and maximum
value, and a new, directed acyclic graph can be created from these component nodes. In graph theory, this new graph is known as the condensation of the original, and happens to be a directed acyclic graph (DAG).
We can now perform a topological sort on the nodes of this DAG, iterating over them in order and updating each node's and
values based on those of the nodes with edges leading to it. For each one, we don't need to bother looking up exactly which initial mines correspond to the component node – only how many there are that have this set of
and
values. This process takes
time.
Finally, we can perform a line sweep to get the requested answers. We'll need events for the civilians' positions, as well as for the start and end of each component node's final explosion range (also storing the number of mines associated with this range). Upon sorting the events in
time, we can iterate over them while maintaining the number of mines whose final explosion range affects the current position, and noting these counts each time a civilian position is reached so that they can later be outputted in the correct order.
Comments