PROBLEM LINKDIFFICULTYMEDIUM PREREQUISITESShortest Path Problem, Dijkstra's Algorithm PROBLEMYou are given N points in a plane. You are given M types of disks. Each disk has some cost associated with it and an infinite supply. You wish to place the disks on the N points (aligning the center of the disk with the points) such that there exists a path that connects the X axis and the line Y = W. QUICK EXPLANATIONLet us formulate this problem in terms of a graph.
Now, we can find the shortest path between the two special vertices N*M + 1 and N*M + 2.
Using the Dijkstra's algorithm to find the shortest path can be found in O(N^{2}*M^{2} + N*M log N*M) time. Of course this is too slow to solve the problem. EXPLANATIONWe notice that the step driving the complexity is the number of edges that must be considered. If we can somehow reduce the number of edges that we must consider, then we can speed up the algorithm. For this, we must first ignore some disks which are redundant. Let the radii and costs of the M disks be represented by the arrays R and C. A disk i is redundant if for some j, R[i] ≤ R[j] and C[i] ≥ C[j]
Thus, we can clean the list of disks as follows stack = [] sort(disks) stack.push(disks[1]) for i = 2 to disks.length while !stack.isEmpty AND disks[i].cost ≤ disks[i1].cost stack.pop() stack.push(disks[i]) Now stack holds the list of disks that should be considered
This particular cleanup allows us to ignore a lot of edges from our original graph. To see why, consider the following three edges
We can assume that
Now, costofedge( (i,j_{1}) to (i,j_{2}) ) = j_{2}.cost  j_{1}.cost costofedge( (i,j) to (p,k_{2}) ) = costofedge( (i,j) to (p,k_{1}) ) + k_{2}.cost  k_{1}.cost Thus, we note that if there is an edge from (i,j) to (p,k_{1}) then the edge from (i,j) to (p,k_{2}) can be ignored since we know it is not going to improve our answer. We will anyway consider the vertex (p,k_{1}) before we would consider (p,k_{2)}. And when we consider the vertex (p,k_{1}) in our algorithm, we will consider the same distance for (p,k_{2}) (or smaller). Note that this is made possible because of the cleanup of the set of disks we did. Lastly, we note that we do not need to consider the edges (i,j) to (i,k) for all k > j. Only doing so for k = j+1 is sufficient. Now, we need a way to find the smallest k for each (i,j) and point p such that there is an edge between (i,j) and (p,k). This can be done in O(N*N*M) time. We will precalculate these values.
After this precalculation the dijkstra's algorithm can be run on this edge set within O(N*M*N log N*M + N*M log N*M) time. This is sufficient to solve the problem. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here. This is a much slower algorithm (due to large constants) intended to verify the answers using an alternate (albeit slower) approach.
This question is marked "community wiki".
asked 21 Jul '13, 15:02

donofgaya thats because we can move from j to j+1 to j+3 ... to any m> J>j answered 29 Jul '13, 23:53

Shouldn't the second line in the following code snippet be (disks[i].cost ≤ stack.top.cost)
answered 01 Aug '13, 12:38

My code has the same time complexity as explained in this editorial and it implements the same logic. But still I am getting TLE(even on using faster I/O in java). Can someone point out an error. Here is a link to my submission. Moreover, the code works even for the worst case input when N = M = 250 and the answer is impossible in each case (WITHIN THE TIME LIMIT). You can see this yourself here. answered 23 Apr '14, 09:55

Are u considering dijkstra's complexity as O(VlogV) in your analysis? Thats achievable only using a fibonacci heap. The general implementation using a priority queue is O(ElogV).
My bad. I fixed it in the last statement of the editorial.
can anyone explain why we need to consider the edge (i,j) to (i,k) for k=j+1 only.??