Dynamic Programming: Cutting SticksTiagoBlockedUnblockFollowFollowingJan 7This article will walk you through a problem called Cutting Sticks¹ from UVA (Universidad de Valladolid)’s problem set².
Read the original problem before continuing this article.
We have a stick (wood) that needs to be cut:The cuts must be done in certain parts of the stick.
You must cut the stick in all marked places.
For example, consider a stick of size 10 and 3 places marked in it (positions 2, 4 and 7) where the cuts must be made.
The cost to make a cut is the same as the size of the stick.
For instance, if you have a stick of size 10 and you need to make one cut (anywhere) in it, that will cost you 10.
It is not difficult to notice that depending on the order you perform the cuts, your total cost will be different.
For example, if you cut the stick on positions 2, 4 and 7 (in this order), the total cost will be 10+8+6=24.
A better way to cut that stick would be by starting on position 4, then 2 then 7.
That would yield a cost of 10+4+6=20,Example of 2 ways to perform the cuts.
Notice the one on the right is better than the left one as the total cost to perform all 3 cuts is smaller.
The problem asks you to find the minimum possible cost given the size of the stick and the places where it needs to be cut.
Let’s define a few things:N: The size of the original stickk: The position (index) where a generic cut is made.
optimalCost(initialIndex, endIndex): A function that returns the best cost to cut a stick that starts in initialIndex and ends in endIndex.
Notice that we want to find optimalCost(0, N).
Here is the key observation to solve this problem.
Whenever we make a cut, we divide the stick into 2 other sticks.
Those 2 new sticks will then need to be cut again (if there is a cut to be made on it) or will remain intact (if there is no further cutting to be made).
Notice that those 2 new sticks that need to be cut represent the same problem again, except that now we have a new stick with a new size and new places (i.
e, new indexes) to cut it.
With that in mind, we just need to find the best way to cut those 2 new sub-sticks and sum their cost with the cost of the original cut you made.
We can equate the above like this:optimalCost(initialStickPosition, endStickPosition) = optimalCost(initialStickPosition, k) + optimalCost(k, endStickPosition) + sizeOfTheCurrentStickHere 'k’is one of the original positions where the stick should be cut.
We also have that sizeOfTheCurrentStick = endStickPosition — initialStickPosition so the final recursive formula is:optimalCost(initialStickPosition, endStickPosition) = optimalCost(initialStickPosition, k) + optimalCost(k, endStickPosition) + (endStickPosition – initialStickPosition)Now we only have to loop through all possible places where the cut can be made (i.
e, all possible'k's)and select the one that yields the minimum cost:Coding nextCutIndex() is trivial and there are many ways to do it, so I won’t pollute the code in this article with it.
With the above, the problem is technically solved, but there is one issue with it: a lot of sub-problems will be recalculated over and over again, making our program slow.
That is where Dynamic Programming can help us.
All we have to do is to store the best cut for the sub-sticks we have found.
Then, the next time we need to find its value, we can just look it up without having to go through the recursion again:Here’m’ is our matrix that will hold the best costs already calculated.
If you don’t do this memorisation step and you try to submit your code on the UVA website, you will get a Time limit exceeded error, meaning your program is too slow to process all test cases they have.
Notice the approach we have taken is a top-bottom one because we start the recursion with the highest stick possible and proceed on cutting it into sub-sticks until there is nothing more to cut.
Sometimes it is easier to think about a DP problem this way.
Nothing stops you from using a bottom-up approach though (as we have done in our first DP article³).
You can find my full C++ implementation here⁴.
Sources:“Cutting Sticks”: https://uva.
onlinejudge.
org/index.
php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944UVA’s problem set index: https://uva.
onlinejudge.
org/index.
php?option=com_onlinejudge&Itemid=8“Dynamic Programming: An induction approach”: https://medium.
com/@tiagot/dynamic-programming-an-induction-approach-b5c5e73c4a19Complete solution: https://github.
com/TheCoinTosser/Competitive-Programming/blob/c3e390a4b7bda82cd6479dfe52d22c7ed3dab405/UVA/10003__Cutting_Sticks.
cpp.