Minimum cost to cut wooden board

Question

Given a wooden board composed of M X N wooden square pieces we need to find the minimal cost of breaking the board into square wooden pieces.

We can cut the board along horizontal and vertical lines and each cut divides the board in smaller parts. Each cut of the board has a cost depending on whether the cut is made along a horizontal or vertical line.

Let us denote the costs of cutting it along consecutive vertical lines with x[1], x[2], …, x[n-1] and along horizontal lines with y[1], y[2], …, y[m-1]. If a cut (of cost c) is made and it passes through n segments, then total cost of this cut will of n*c.

The cost of cutting the whole board into single squares is the sum of the cost of successive cuts used to cut the whole board into square wooden pieces of size 1x1.

Whats the minimal cost of breaking the whole wooden board into squares of size 1x1.

Example : Let us take 6*4 grid.

Let cutting along rows cost is as follow : [2 1 3 1 4]

Cutting along column cost as follow : [4 1 2]

Here answer will be 42

We should start cutting using y5, x1, y3, y1, x3, y2, y4 and x2, in order. First cut will be a horizontal one where cost = y5 = 4. Next we will do a vertical cut with x1. Since this cut passes through two segments (created by previous vertical cut), it’s total cost will be 2*x1 = 2*4. Similarly next horizontal cut (y3) will pass through two segments and will cost 2*y3 = 2*3. We can proceed in similar way and get overall cost as 4 + 4*2 + 3*2 + 2*2 + 2*4 + 1*3 + 1*3 + 1*6 = 42.

My Approach : Check for each cut starting from cut between 1 and 2 nd row then so on.But obviously its too inefficient.So how to solve this problem?

Answer 1

The selection of the split lines should be in decreasing cost order for achieving minimal total cost.

Proof:

Any "incorrectly" ordered sequence of cuts must have 2 consecutive cuts C1 and C2 with costs c1 and c2, such that c1<c2 and C1 comes before C2. If the two cuts are parallel to each other, then switching their order has no effect on the total cost.

If on the other hand C1 is vertical while C2 is horizontal (without loss of generality), then we can examine it as follows. Let V0 be the number of vertical fragments before C1 is applied, and H0 be the number of horizontal fragments prior to C1.

• The cost of applying C1 and then C2 is: H0*c1 + (V0+1)*c2
• The cost of applying C2 and then C1 is: V0*c2 + (H0+1)*c1

The first expression minus the second gives c2-c1, which is positive. In other words, swapping C1 and C2 reduces the cost.

Conclusion: Using a series of swaps, any non-ordered sequence can be transformed into an ordered one, such that the total cost can only be reduced. This completes the optimality proof.

Note: In case of multiple cuts with the same cost, their internal ordering doesn't affect the total cost at all, as seen in the calculation above.

Answer 2

Though the question was already answered, I am writing this to offer an informal, may be intuitive explanation:

We have to make (n-1)*(m-1) cuts, so we just need to decide on which cut to pick first.

Let us say we can have to choose between two cuts C1 and C2 with cost c1 and c2. Let us say c1>c2. Let the total current cost of the whole affair be denoted by C

If we choose C1 later than this step, it will add at least (depending on if you add it in the very next step or not) c1 to the whole cost, C. If we choose C2 later than this step, it will add at least c2 to the whole cost, C.

So we can just say that we can greedily choose C1 now because choosing it later would be worse than choosing C2 later.

Hence we choose in decreasing order of costs irrespective of type(horizontal, vertical) of cut.

Answer 3

Here is my Greedy Algorithm approach in Python 2.

1. To minimize cost, the most expensive locations must be cut first
2. The number of times to cut is (M - 1) + (N - 1)
3. Internal order doesnt matter. Because eventually all of the locations will be cut
4. Keep track of the current number of cuts in each dimension (nx,ny)

Code

M,N = [int(x) for x in raw_input().split()]
CY = sorted([int(x) for x in raw_input().split()], reverse=True)
CX = sorted([int(x) for x in raw_input().split()], reverse=True)
nx = 1
ny = 1
minC = 0
i = 0
j = 0
total = M - 1 + N - 1
for _ in range(0,total):
    #j == N - 1 to check if CX is exhausted
    if (j == N - 1 or (i != M -1 and CY[i] > CX[j])):
        minC += CY[i]*nx
        ny += 1
        i += 1
    else:
        minC += CX[j]*ny
        nx += 1
        j += 1

print minC%(1000000000+7)

Answer 4

This problem can be solved by Greedy Algorithm approach.

Only 1 rule :- Select the cutting cost in decreasing order, if two or more cost are equal, select any. Here is the python solution:-

M, N = map(int, raw_input().strip().split(' '))
Y = map(int, raw_input().strip().split(' '))
X = map(int, raw_input().strip().split(' '))

Y.sort(reverse=True)
X.sort(reverse=True)

y_cut = x_cut = 1     #To count the number of segments
cost = i = j = 0

while i < X.__len__() and j < Y.__len__():
    if X[i] >= Y[j]:
        x_cut = x_cut + 1
        cost = cost + (X[i]*y_cut)
        i = i+1
    else:
        y_cut = y_cut + 1
        cost = cost + (Y[j]*x_cut)
        j = j+1

while i < X.__len__():
    cost = cost + (X[i]*y_cut)
    i = i+1

while j < Y.__len__():
    cost = cost + (Y[j]*x_cut)
    j = j+1

print cost

Answer 5

Just select cutting lines in decreasing cost , here is the code in c++

Code :

#include <bits/stdc++.h>
using namespace std;

int main() {
long int t;
cin >> t;
while(t--){
    long long int m,n,*x,*y,i,j,sum,cx,cy,modu = 1000000007;
    cin >> m >> n;
    x = new long long int[m-1];
    y = new long long int[n-1];
    for(i=0;i<m-1;i++)
    cin >> x[i];
    for(i=0;i<n-1;i++)
    cin >> y[i];
    sort(y,y+n-1);
    sort(x,x+m-1);

    i=m-1-1;sum=0;j=n-1-1;cx = 1;cy =1;
    while(i>=0 && j >=0){

         if(x[i] > y[j]){
            sum += (x[i]*cy)%modu;
            cx++;
            i--;
        }
        else{
            sum += (y[j]*cx)%modu;
            cy++;
            j--;
        }
    }

    while(i>=0){
        sum += (x[i]*cy)%modu;
        i--;
    }
    while(j>=0){
        sum += (y[j]*cx)%modu;
        j--;
    }

    cout << sum%modu << endl;
}
return 0;
}

Answer 6

Well, it seems that this is quite simple. Hence you need to do all the cuts and minimize number of most costly cuts, you should just order them by their cost.

There's a catch though - if you have cuts priced same, then you need to group them. Let's say you have to make 5 cuts priced 6 each, 4 on columns, 2 on rows and board is uncut. If you cut 2 rows first, your cost is 2 * 6 + 4 * 3 * 6 = 14 * 6. If you do it other way around, you get 4 * 6 + 2 * 4 * 6 = 12 * 6.

Rule is do high priced cuts first and first along axis that there are most of them.

EDIT: To keep track of how many segments you have, you need to track cuts you made to other axis. o if you have made 3 cuts on rows, then cutting column will require 3 + 1 cuts. If you have already cut 5 colums and 3 rows, cutting another row will always have to go through each column cut line meaning you have to cut 5 + 1 times.

EDIT 2: Since my example is not right, this is how it looks like using situation from question:

cut_x = [2, 1, 3, 1, 4]
cut_y = [4, 1, 2]

list_of_cuts_grouped_by_cost_descending = [[x5, y1], [x3], [x1, y3], [x2, y2, x4]]

cut_groups_ordered_by_most_cut_axis = [[x5, y1], [x3], [x1, y3], [x2, x4, y2]]

return cut_groups_ordered_by_most_cut_axis.flatten