RIVPILE - Editorial

PROBLEM LINK

Practice
Contest

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.

2 Likes

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).

2 Likes

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.??

donofgaya thats because we can move from j to j+1 to j+3 … to any m> J>j

Shouldn’t the second line in the following code snippet be (disks[i].cost ≤ stack.top.cost)

for i = 2 to disks.length
    while !stack.isEmpty AND disks[i].cost ≤ disks[i-1].cost
        stack.pop()
    stack.push(disks[i])

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.