Variant of Rod Cutting Problem (DP)

#1

I am trying to solve this problem:

There is a rod of length N lying on x-axis with its left end at x = 0 and right end at x = N. Now, there are M weak points on this rod denoted by positive integer values(all less than N) A1, A2, …, AM. You have to cut rod at all these weak points. You can perform these cuts in any order. After a cut, rod gets divided into two smaller sub-rods. Cost of making a cut is the length of the sub-rod in which you are making a cut.

Your aim is to minimise this cost. Return an array denoting the sequence in which you will make cuts. If two different sequences of cuts give same cost, return the lexicographically smallest.

This question is a variant of Rod cutting problem and is often asked in Google interviews. Thus, this question is also well studied. I found posts on Stackoverflow and GeeksForGeeks about this question but I am still at loss to understand because these solutions are directly implemented bottom up.

To get a sense of how this question is to be thought, I am looking for a simple recursive solution first.

1 Like
#2

You can try doing it recursively by keeping account of the sub-rod which is going to be cut, and passing the array M weak points also alongwith it.
At last you’ll have to take minimum of all the recursive calls to get answer.

#3

Could you please describe the pseudo code?

#4

Hey!
Firstly, for solving this problem we are taking two 2D arrays :
array1 -> to store the best index at which we should make the cut between two given indexes
array2 -> to store the best result we will be getting if we make a cut at the best suitable index between two given indexes

Now, how the recurrence is working in this problem is the main concern,
So, here we have an array of weak points, we call our recurrence function on that array and passes the first and last index. Let’s say array as A of size 4 so we call recurrence(0,3).
Now inside our recurrence function, we work only when left_index < right_index, and what we do is
1 -> if already there is an answer stored in array2 for the given left and right index, then we don’t do anything and just return… but if there is no answer stored in array2 for the given left and right index, then
- we iterate between the left and right index, and let A[i] be the index where we have to make the cut… so
we seek for the best answer which we will be getting if we make a cut on index A[i], for that we call our
recurrence() recursively and get the answer for (left, i) and (i, right) also add the work we are doing for A[i]
i.e. A[r] - A[l], then add all of these as
best_ans_for_index_i = recurrence(l, i) + recurrence(i, r) + A[r] - A[l]
best_index = i
then we store the minimum best_ans_for_index_i and best_index in array2 and array1 respectively
corresponding to given (l, r).

After completion of recurrence function we are supposed to print the lexicographically smallest sequence of the indexes… we can do that using the array1 which we have filled in recurrence function as shown below

solution (left , right){

if (left >= right-1 )
         return;

        print ( A[ array1 [ left ][ right ] ]);

solution( left, array1[ left ][ right ] );
solution( array1[ left ][ right ], right);

}
we are supposed to print the solution lexicographically so we first make the recursive call for the left part and then for right part.

I hope this explanation will be helpful for you to understand how recurrence and DP is working for this problem. :slight_smile:

1 Like
#5

This is great explanation. I had solution, but understood with this explaination
Anyway, here is the working solution

typedef struct stelem
{
    int cutPos;
    int start;
    int end;
}stelem;

vector<int> Solution::rodCut(int A, vector<int> &B) {
    
    int i, l, k, size;
    sort(B.begin(), B.end());
    vector<int> :: iterator it = B.begin();
    B.insert(it, 0);
    B.push_back(A);
    size = B.size();
    
    vector<vector<pair<long long, int> > > memo(size, vector<pair<long long, int> >(size, make_pair(0, -1)));

    // memo[i][j] = min cost of cutting a rod starting from i to j
    // = (j-i) + min (memo[i][k] + min[k][j]) where k is each cut b/w i and j
    // memo[0][A] = min cost of cutting the complete rod

    // Fill based on the number of cuts starting 1
    for(l=0; l<size-1; l++)
    {
        for (i=l+1; i<size; i++)
        {
            // start = i-l-1, end = i;
            int s = i-l-1;
            int e = i;

            if (l == 0)
            {
                memo[s][e].first = 0;
                memo[s][e].second = -1;
            }
            else
            {
                // k = start+1 to end-1
                long long temp = LONG_MAX, val;
                int cutPos = -1;
                for (k = s+1; k < e; k++)
                {
                    val = memo[s][k].first + memo[k][e].first;
                    if (temp > val)
                    {
                        temp = val;
                        cutPos = k;
                    }
                }
                memo[s][e].first = (long long)(B[e]-B[s]) + temp;
                memo[s][e].second = cutPos;
            }
        }
    }

    // Figure out the cut sequence
    stack<stelem> st;
    vector<int> result;
    // push first stelem
    if (memo[0][size-1].second != -1)
    {
        stelem t;
        t.cutPos = memo[0][size-1].second;
        t.start = 0;
        t.end = size-1;
        st.push(t);
    }

    while(!st.empty())
    {
        // pop top element
        stelem temp = st.top();
        st.pop();
        result.push_back(B[temp.cutPos]);

        // Push right part (cutPos - End)
        if (memo[temp.cutPos][temp.end].second != -1)
        {
            stelem right;
            right.cutPos = memo[temp.cutPos][temp.end].second;
            right.start = temp.cutPos;
            right.end = temp.end;
            st.push(right);
        }

        // Push left part (start - cutPos)
        if (memo[temp.start][temp.cutPos].second != -1)
        {
            stelem left;
            left.cutPos = memo[temp.start][temp.cutPos].second;
            left.start = temp.start;
            left.end = temp.cutPos;
            st.push(left);
        }
    }

    return result;
}
1 Like