1
$\begingroup$

We have a broken stick. For every part, we know it's length. Our task is to connect all parts (glue them), that we will use as small amount of glue as possible.

The amount of glue need to connect two parts equal the maximum from their sizes. We can only glue two parts at one time.Can we solve this problem in the time complexity smaller than $O(n^3)$? I know only the answer, using dynamic table in this complexity

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Do the parts have a fixed position (in the "reconstructed" stick)? Or can they be rearranged arbitrarily? $\endgroup$
    – Vor
    Jan 9, 2013 at 15:36
  • 1
    $\begingroup$ If I understand correctly, the problem looks like the construction of a Huffman tree. If so, the problem would be solved in O(n log n) time. $\endgroup$
    – Yoshio Okamoto
    Jan 9, 2013 at 16:03
  • 3
    $\begingroup$ Could you please explain why you are interested in this question and provide motivation? $\endgroup$
    – Kaveh
    Jan 9, 2013 at 16:23
  • 1
    $\begingroup$ @MarzioDeBiasi - No, the parts have fixed order in the glued stick. $\endgroup$
    – Jonny
    Jan 9, 2013 at 23:21
  • 2
    $\begingroup$ I have given very similar questions in homework and exams in my undergraduate algorithms course. This should be migrated to CS.SE. $\endgroup$
    – JeffE
    Jan 10, 2013 at 8:53

2 Answers 2

Reset to default
1
$\begingroup$

You didn't define what 'connecting all parts' is. Do you need to arrange them in an array? Or just connect them?

The way I understood the problem, you can use Prim's algorithm to find the minimum spanning tree, and that's the result. O(n^2)

In case you want them arranged in an array, I think the sorted array is always optimal.

We will call a part "counted" if it is the bigger part in some connection. A part can be counted 0, 1, or 2 times. Let there be 3 elements in the array that are not sorted (A > B > C). Let L be the part placed left from this sequence, and R the part placer right. The ordering is L(permutation(A,B,C))R. You can observe all cases, and see that the permutation ABC is the best because it takes the parts max(L,A), A, B, max(C,R). This proves that all 3 element subsequences should be sorted, which means the sorted array is optimal.

Improve this answer
$\endgroup$
0
4
$\begingroup$

Homework?

See the problem "Cutting Wood", which involves cutting rather than glueing, but is otherwise equivalent. Provided the orders matters (as noted by Marzio).

Your favorite sawmill charges by length to cut each board of lumber. For example, to make one cut anywhere on an 8 ft. board of lumber costs \$8. The cost of cutting a single board of wood into smaller boards will depend on the order of the cuts. As input, you are given a board of length $n$ marked with $k$ locations to cut

solution to exercise (pdf) Found in several places on the web, don't know the original.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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