There is a river which can be considered as an infinitely long straight line with width W.

There are A piles on the river, and B types of wooden disks are available. The location of the $i$-th pile is $(X_i, Y_i)$.

The $i$-th type of wooden disks has radius $R_i$, and its price is $C_i$ per disk.

Disks can be placed on the river such that for each wooden disk, its center must be one of the locations $(X_i, Y_i)$ of piles. We can only move on the wooden disks.

How to find the minimum cost such that we can cross the river.I am unable to approach questions like these. What would be the best method to approach this one?

I have come to realize that we can use Dijkstra's algorithm here. We treat this as a graph, with piles as the nodes. Start point can be $y=0$. and $y=W$ as the end point. But i am having implementation problems. There are multiple disks which can be used in going from on state to another. How to handle this?

  • $\begingroup$ How many wooden disk do you have (for each type)? infinite? $\endgroup$ – user742 Aug 14 '13 at 13:54
  • 2
    $\begingroup$ This question seems like it is missing something. So, you've got i piles, and you can pick up a disk from any pile, but then you have to place it centered on a pile? You can't spread them out from there, or drop them anywhere that touches another pile? What if the shortest distance between any two piles is greater than two of the largest disk available? Are we guaranteed a solution? $\endgroup$ – Nobbynob Littlun Aug 15 '13 at 1:17

I'm sure someone will manage to come up with a more efficient idea, but here's a basic one:

  1. Have both sides of the river be nodes in the graph. Define the disk used for these nodes as having 0 cost and 0 radius.
  2. Split each pile into B nodes in the graph, one for each type of disk.
  3. Connect each pair of nodes where the sum of the radius of the 2 disks of these nodes is less than or equal to the distance between the nodes.
  4. Define the cost of an edge as the cost of the disk of the destination node. The cost of the source node will already have been included in the previous step.
    Note that this should be dynamically calculated - one can approach an edge from either side, thus it can take on the value of either node, thus could have different costs at different times.
  5. Run Dijkstra's algorithm as per usual from the source side of the river.

One can get a more efficient but more complex algorithm by only having a single node for each pile and storing the radius of the chosen disk at each point.

Note that any disk type A with cost cA and radius rA can be discarded if there exists a disk type B with radius rB >= rA and cost cB <= cA, or, equivalently, if there's a bigger and cheaper disk type, since it would always be more efficient to use that one instead.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.