PROBLEM LINK
DIFFICULTY
MEDIUM
PREREQUISITES
Shortest Path Problem, Dijkstra’s Algorithm
PROBLEM
You 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 EXPLANATION
Let us formulate this problem in terms of a graph.
- There are N*M + 2 vertices
- Each vertex represents a selection of a disk for a particular point
- An edge exists between two vertices (i, j) and (p, q) iff
- distance-between(i, p) ≤ j.radius + q.radius
- cost of edge = q.cost
- The first special vertex represents the X-axis. Vertices (i, j) are connected to the X-axis iff
- i.y-coordinate ≤ j.radius
- cost of edge = j.cost
- The second special vertex represents the line Y = W. Vertices are connected to this line iff
- y-cooridinate + radius ≥ W
- cost of edge is 0
Now, we can find the shortest path between the two special vertices N*M + 1 and N*M + 2.
- Number of vertices = O(N*M)
- Number of edges = O(N2*M2)
Using the Dijkstra’s algorithm to find the shortest path can be found in O(N2*M2 + N*M log N*M) time.
Of course this is too slow to solve the problem.
EXPLANATION
We 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]
- Using a disk of greater radius is cheaper
- If there is a solution that uses disk i, then you can replace each instance of disk i with disk j without affecting the answer
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[i-1].cost
stack.pop()
stack.push(disks[i])
Now stack holds the list of disks that should be considered
- in increasing order of radii
- in increasing order of cost
This particular cleanup allows us to ignore a lot of edges from our original graph. To see why, consider the following three edges
- From (i, j1) to (p, k1)
- From (i, j1) to (p, k2)
- From (i, j1) to (i, j2)
We can assume that
- k1 < k2
- i ≠ p
Now,
cost-of-edge( (i,j1) to (i,j2) ) = j2.cost - j1.cost
cost-of-edge( (i,j) to (p,k2) ) =
cost-of-edge( (i,j) to (p,k1) ) + k2.cost - k1.cost
Thus, we note that if there is an edge from (i,j) to (p,k1) then the edge from (i,j) to (p,k2) can be ignored since we know it is not going to improve our answer. We will anyway consider the vertex (p,k1) before we would consider (p,k2). And when we consider the vertex (p,k1) in our algorithm, we will consider the same distance for (p,k2) (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.
- Iterate over all values of i
- Iterate over all values of p
- For each i and p, we can iterate over j
- As j increases, k will decrease
- Thus we can find in O(M) time the smallest k which connects (i,j) and (p,k)
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 SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here. This is a much slower algorithm (due to large constants) intended to verify the answers using an alternate (albeit slower) approach.