Dappy is given a metal bar of length a. He can divide a metal bar at any point into two smaller metal bars, such that their lengths sum up to the original length. This process takes some time though, proportional to the length of the metal bar. If he wants to split a metal bar of length x, that will take x minutes.
Coffey comes along and orders n metal bars. He wants the kth metal bar to be of length $z_{k}$ and luckily for Dappy,
$$\sum_{k=1}^{n} z_k = a$$
holds.
Find the fastest algorithm for Dappy to fulfill Coffey's order and prove that it is the fastest.
Here is my answer
I'm not sure if there is a nice answer in general. A trivial (exponential time) algorithm is using subset dynamic programming; Since Dappy cannot merge bars, he must make exactly $n-1$ moves, and in the first move he must break $a$ into $\sum_{i \in S_1} z_i$ and $\sum_{i \in S_2} z_i$ where $S_1, S_2$ partition $[n].$ So if $f(b_1,\ldots,b_m)$ is the optimal time for the task of breaking a bar into $m$ bars of sizes $b_1,\ldots,b_m$ then we have $f(z_1, \ldots, z_n) = a + \min_{S_1, S_2} f((b_{S_1})) + f((b_{S_2})),$ and base cases are $f(z) = 0$ (single bar do nothing.)
Maybe we can reduce some NP-hard problem to this.
Can someone help me to find the fastest algorithm for the problem ? (Any other ways to solve the problem(i am thinking of building a Huffman tree))
Edit:-mihaild answerd my question already but if anyone another idea then please share
Indeed, Huffman tree is the way to go.
Assume that we have some way of cutting, it can be represented as binary tree, where leaves are bar that we want to get. If this tree is optimal, any tree that we get from it by merging some subtree into a single node is also optimal (otherwise take some tree that is better, and unmerge this node).
Every leaf contributes it's length multiplied by it's depth to the total sum. We can show that there is an optimal tree, in which two shortest bars are merged together: take some optimal tree, find the deepest non-leaf node in it, and swap it's children with shortest and second-shortest leafs - this will not increase total cost of the tree. So, to build an optimal tree, we can start by merging two shortest bars together, and then continue.
If you implement this algorithm using some efficient heap structure, you will get $O(n \cdot \log n)$ time.