If data structure augmentation and designing algorithms give you a high and you wish to post in this forum email me(Inder) at inder.pall@gmail.com
DISCLAIMER : questions posted here could be from multiple source, i'll try my best to provide credit.
you are given n ropes,maybe of different length. the cost of tying two ropes is the sum of their lengths.Find a way to tie these ropes together so that the cost is minimum.
not really, initally i thought the same. However say if you if you have three ropes
x, y, z wherein x < y < z
if you tie y+z first then you tie x+ y +z which is essentially x + 2* (y+z)
so all ropes which have been tied before actually keep adding to the cost again and again. Hence the best strategy would be to include smaller ropes initially so that they contribute lower cumulative cost in future
It may be done using the Huffman tree approach. Keep all the ropes in a min heap. Delete top 2, join them and push the new rope in the heap. Repeat until a single rope is left.
6 comments:
Since the cost of tying two ropes is not constant, isn't the total cost always going to be the sum of length of all ropes?
(I'm assuming the cost function applies the same to intermediate ropes you get after you tie them together)
not really, initally i thought the same. However say if you if you have three ropes
x, y, z wherein x < y < z
if you tie y+z first
then you tie x+ y +z which is essentially x + 2* (y+z)
so all ropes which have been tied before actually keep adding to the cost again and again. Hence the best strategy would be to include smaller ropes initially so that they contribute lower cumulative cost in future
It may be done using the Huffman tree approach. Keep all the ropes in a min heap.
Delete top 2, join them and push the new rope in the heap.
Repeat until a single rope is left.
I like the solution of keeping it in min heap....
The heap solution appears the best.
Post a Comment