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.