Introducing the problem
-----------------------
It is pretty obvious that for smaller bounds this problem is easily solvable
through a depth first search type of approach or even floyds. We can think
of this problem as a directed graph problem where the cans are the nodes and
the edges from can i to can j are added if an explosion from can i can reach
some can j. There are two issues with a dfs approach for this problem. One
such a graph could potentially have N^2-N edges and two we would need to run
N such dfs procedures to calculate the information. Worst case runtime for
such a "brute force" approach can be up to V*(V+E) or N^3 in terms of this
problem.
Introducing solution ideas
--------------------------
This problem has two different solutions. One solution requires that the
contestant make some observations about the structure of the problem and
code a reasonable runtime solution. The first solution is also easier to
code and requires no special knowledge to solve this problem.
The second solution requires some shared oberservations as the first solution
but then requires some graph theoric knowledge on reachability problems
to solve. This solution is harder to code but has a big O runtime.
The first solution
------------------
Let us first make the observation that this problem in the general sense is
hard to get a fast enough solution. We simply do not have enough time to
construct the large graph. Eventually you get the following idea. Is it easier
to solve if the explosions only go in one direction. We can only go right or
only go left. What we notice is the union of these two graphs is the graph we
are looking for.
Instead of building the large N^2 graph we need to build a graph with order N
edges or close to it. We can make the following observation about building a
graph using only rightward edges. When adding an edge to the right to some can
j we do not have to add any edges to any of the cans that j can reach! The second
obeservation is that the if we can reach some can j from i then we can reach
all cans whose location are between j and i.
Because of these oberservations we can use the following algorithm to produce
the right edge only graph.
create a stack named stk
sort all cans by x coordinate in decreasing order
for each can curCan
{
while (canReach(curCan, stk.top))
{
add edge between curCan and stk.top
pop stk
}
push curCan onto stk
}
Notice that the algorithm uses a stack to maintain only the "head" of each
path to other cans. Once an edge is added there now exists a closer can for
each edge going right on the top of the stack. We no longer have to consider
the can at the top of the stack so we remove it. Notice that this means
the in degree of each can is at most one since edges are only added when a
can is popped. A graph created this way will have at most N edges. This
is because the sum of the in degrees equals the number of edges.
We can do the same procedure to make the graph that moves left. In total our
union graph will have at most 2*N edges.
Now consider the following obervation. In O(N) time we can determine the farthest
right can we can reach only using right edges! We simple move from right to left
on the cans. When a can is reach we update the furthest right it can go by
taking the maximum of all cans it can reach in our reduced graph. This same
property holds true for our left graph.
Awesome we almost have a solution! But we have the following issue. Our strategy
doesn't work on the union graph. Notice we can have a path that is some
combination of left and right moves and can reach further right than a move
of just one can.
Example:
------9-2----1-------
Notice the can of blast radius 2 can reach the far right can by going through
the can of blast radius 9. Let us for convenience call such a path a zig zagging
path.
Let us do some analysis of zig zagging paths. Let us call a zig zagging path
reduced if that path strictly alternates between left and right edges. Let us
call it skimpy if it is the only path between two cans. Let us
observe an example reduced skimpy zig zagging path:
.______.
| .. |
| || |
--------------15---31-7-----29----------
| | | |
| .__. |
._____________.
Notice how with each can we must clear a given blast diameter of another can?
Otherwise we would have a blast going in the rightward direction that would
hit the can we are trying to hit with out leftward blast. Notice how skimpy
paths force the length travelled to double each time or they will not force
a zigzag path to require to be taken.
With that we make the following oberservation. Put an objective to minimize
the number of times the path changes directions. What is the shortest path
(in terms of the number of direction changes) between two cans i and j. We
can guarantee that this value will never be more than log(M) where M is
the coordinate space of the fence. The log(M) restriction is because the
blast radius must double in each step.
With that we can solve with the following simplified algorithm
array farthestRight
array farthestLeft
while (answers have changed since last sim)
{
update farthestRight and farthestLeft using only right edge moves
update farthestRight and farthestLeft using only left edge moves
}
for each can curCan
print farthestRight[curCan]-farthestLeft[curCan]+1
The while loop will run at most 2*log(M) (base 2) times. Our algorithm is simply
O(N * log(M)). This runtime is fine since M is at most 10^9.
The second solution
-------------------
The second solution is similar to the first up to a point. We follow the first solution
until we can create the union graph that has at most 2*N edges. From there
we will actually use the built union graph.
We can make the following observation. Consider two cans i and j. If can i can
reach can j and can j can reach can i then can i and can j will be able to reach
the same furthest right and left cans. These two cans are in the same strongly
connected component. We can compress the given graph into a meta graph of
strongly connected components. Notice this meta graph contains no cycles because
if it did they would be in the same strongly connected component. We can run a dynamic
programming procedure on this meta graph and determine the furthest left and right
we can reach. The meta graph can be built in V+E or N in this problem using any
of the various dfs modifications that can produce strongly connected components.
The total runtime is O(N) for this version.