Board cutting problem

To cut a wooden board, a sawmill charges proportional to the length of the board. The cost of cutting a single board into many smaller boards will thus depend on the order of the cuts. As an example, lets say cutting a $10m$ board into two pieces costs $10$. Then to cut a $10m$ long board at marked positions $3m$ and $5m$ costs $10+7=17$ if it is ﬁrst cut at position $3m$ and then at $5m$. On the other hand, if it is cut at $5m$ position ﬁrst, and then at $3m$, it would cost $10+5=15$. As input, you are given a board of length $n$ with $k$ marks on it. You need to give an algorithm that, given an input length $n$ and a set of $k$ desired cut points along the board, will produce a cutting order with minimal cost in $O(k^c)$ time, for some constant $c$

I'm getting $O(k!)$ complexity :(

• To me, the way this sawmill calculate the cutting cost is unnatural. An equivalent problem: Given a sequence of integers, find the order of summing integers one adjacent pair at a time such that the total cost of summing into one integer is lowest. The cost of doing each summation is the size of the result. – Apiwat Chantawibul Aug 17 '14 at 6:16
• @Biliska is right, it took me a while to understand the question , but your hint really helps me. This looks like a classic dynamic programming question with solution being $O(k^3)$. Building a 2 dimensional array to hold temporary values, and each temporary value needs at most k iterations on other temporary values to be computed. – InformedA Aug 17 '14 at 6:58
• You tag dynamic-programming but have not shown any attempt in that direction (I take it $O(k!)$ is from the naive brute-force algorithm). So try something yourself; where do you get stuck? – Raphael Aug 17 '14 at 8:51

To me, the way the cutting cost analogy is unnatural. I'm going to work with an equivalent problem instead. Additionally, I'll think about the task in reverse, combining pieces instead of cutting.

An equivalent problem:

Given a sequence of integers $s_0,s_1,\ldots,s_k$. We want to find the order of adding up all the integers such that the cost of this process is minimize. The add operation only works on each adjacent pair in the sequence and will replace the pair with its sum. The cost of each add operation is the resulting sum.

I'll think about the problem of finding lowest cost first. The order of adding can be traced back if you have the algorithm to find the lowest cost.

Define $M(i,j)$ to be the lowest cost of this process on the subsequence

$s_i,s_{i+1},s_{i+2}\ldots,s_{j-2},s_{j-1},s_j$

where $0 \le i \le j \le k$

We can then formulate $M(i,j)$ in terms of smaller problems as follows:

$M(i,j) = \Sigma_{y=i}^{j} s_y + \min\limits_{x \ldotp i \leq x < j} \{M(i,x) + M(x+1,j) \}$

for the case that $j-i>2$

I'll leave the base case of $j-i \le 2$ and the order of which $M(i,j)$ to calculate first for reader to work out.

The algorithm has to calculate $M(i,j)$ for every $0 \le i \le j \le k$ and each time it does that, it has to iterate over $x$. Thus, the time complexity is $O(k^3)$

• Shouldn't be $M(i,j)=S_j-S_i+min_{i\leq x\leq j} \{M(i,x)+M(x,j)\}$ ? – James Yang Aug 17 '14 at 7:09
• Minor point, it looks like you want $M(i,j) = \Sigma_{y=i}^{j} s_y + \min\limits_{i \leq x < j} \{M(i,x) + M(x+1,j) \}$ instead? – InformedA Aug 17 '14 at 7:11
• @James Yang That is the formula for your version of the question. His answer changes the question a bit. – InformedA Aug 17 '14 at 7:13
• Please consider not to encourage undesirable posting behaviour. – Raphael Aug 17 '14 at 8:52