Editorial for CCC '15 S4 - Convex Hull - DMOJ: Modern Online Judge

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]$ ~dist[i]~ containing the shortest distance from the source to node $i$ ~i~, we will instead define $dist[i][j]$ ~dist[i][j]~ to be the minimum distance from the source to node $i$ ~i~ while sustaining exactly $j$ ~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$ ~1~, and there exists an edge to node $2$ ~2~ with length 3 that deals 4 damage to your hull. Then, $dist[2][j+4] = dist[1][j]+3$ ~dist[2][j+4] = dist[1][j]+3~ for all $(0 \le j < K-4)$ ~(0 \le j < K-4)~.

Then, we can simply loop through all possible amounts of damage less than $K$ ~K~, and take the best distance to node $B$ ~B~ given $j$ ~j~ damage $(0 \le j < K)$ ~(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$ ~K~ from considering all damages at each node. The time complexity is $\mathcal O(K (M + N \log N))$ ~\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

-3
jiapei100 commented on Nov. 12, 2021, 5:20 a.m.
From the Sample Input 1,

10 4 7 1 2 4 4 1 3 7 2 3 1 8 1 3 2 2 2 4 2 1 6 3 4 1 1 1 4 6 12 1 4

particulary, line 3 and 4:

1 3 7 2 3 1 8 1

Can we make a conclusion that this is a directional map, instead of an undirectional map?

Thank you ...

4

4fecta commented on Nov. 12, 2021, 9:28 a.m.

You may find it useful to reread the statement. In particular:

"... the $i^{th}$ ~i^{th}~ route runs directly between two different islands $a_i$ ~a_i~ and $b_i$ ~b_i~; ( $1 \le a_i, b_i \le N$ ~1 \le a_i, b_i \le N~), takes $t_i$ ~t_i~ minutes to travel along in either direction, and has rocks that wear down the ship's hull by $h_i$ ~h_i~ centimetres. There may be multiple routes running between a pair of islands."

-2

zhenga1 commented on Feb. 15, 2021, 1:38 a.m.

Why do you set inq[spot] = False every time you pop from the queue?

3

Kirito commented on Feb. 15, 2021, 2:46 a.m.

Note that I use a boolean array called inq here to store whether a node is already in the priority queue.

3

sunnylancoder commented on Feb. 21, 2017, 8:28 p.m.

When I submitted the solution with the boolean array to prevent duplicates in the queue, it got 12/15 (WA). Then I submitted removing the boolean array, and got 14/15...not sure why.

Also, why do you sort the priority queue from greatest to least? Shouldn't it be the other way around?

0

JohnstonLiu commented on Jan. 26, 2021, 3:36 p.m.

Usually when you use a priority queue for dijkstras you put in negative values for distance so that it sorts from greatest to least. He didn't put in negative values so he instead sorted the priority queue from greatest to least.

3

omaewamoushindeiru commented on May 22, 2015, 1:38 a.m. ← edit 3 →

If anyone is interested! Also, thanks to kobortor for being awesome.

Editorial

1

fifiman commented on May 22, 2015, 1:58 a.m.

Sadly BFS does pass, and all the additional structs aren't necessary

1

kobortor commented on May 22, 2015, 7:05 a.m. ← edit 2 →

why sadly, since its so fast isn't it the intended solution?

Edit: NVM I'm blind, I just like to use structs to organize things in my code.