Editorial for CCC '15 S4 - Convex Hull


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

by Andrew Li

We can see that this is simply a shortest path question with the added constraint that the hull damage must not exceed a certain amount.

We can still use Dijkstra's algorithm, except the distance array needs another dimension. Instead of dist[i] containing the shortest distance from the source to node i, we will instead define dist[i][j] to be the minimum distance from the source to node i while sustaining exactly j cm of damage.

With this in mind, we need to alter Dijkstra's algorithm. Normally, after popping a node from the priority queue, you would loop through all adjacent nodes, updating the shortest path to each adjacent node. For this question, we must consider all adjacent nodes, but also all possible amounts of damage we have currently sustained on the hull. To update an adjacent node, see the following example. Assume you are at node 1, and there exists an edge to node 2 with length 3 that deals 4 damage to your hull. Then, dist[2][j+4] = dist[1][j]+3 for all (0 \le j < K-4).

Then, we can simply loop through all possible amounts of damage less than K, and take the best distance to node B given j damage (0 \le j < K).

Note that I use a boolean array called inq here to store whether a node is already in the priority queue. This saves a lot of time as it prevents numerous copies of the same node from being stored in the queue at once.

Thus, the time complexity is the same as for Dijkstra's, except for the factor of K from considering all damages at each node. The time complexity is \mathcal O(K (M + N \log N)), which will run in time.

Alternate Solution

This is a multigraph, and according to a wise computer science teacher, it cannot be solved except with 3-D dynamic programming. Okay, I give up! There is no way to solve this! Clearly, this was not designed for the average high school student!


Comments

There are no comments at the moment.