Last Updated: 5 Feb, 2021
Break The Board
Easy
Asked in companies
You’re given a board of length 'L' and width 'W'. Your task is to break this board into 'L' * 'W' smaller squares, such that the total cost involved in breaking is the minimum possible.
NOTE:
The breaking cost of each edge for the board will be given.
Input Format:
The first line of input contains 'T', the number of test cases.
The first line of each test case contains two space-separated integers 'L' and 'W', denoting the length and width of the box.
The second line contains 'L' - 1 space-separated integer, where the 'ith' integer denotes the cost of one horizontal cut between the rows 'i' and 'i' + 1.
The third line contains 'W' - 1 space-separated integer, where the 'ith' integer denotes the cost of one vertical cut between the columns 'i' and 'i' + 1.
Output Format:
The only line of output of each test case should contain an integer denoting the minimum cost required to break the board into 'L' * 'W' squares.
Note:
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
2 <= L, W <= 10 ^ 4
1 <= costL[i], costW[i] <= 10 ^ 5
Time Limit: 1 sec
Approaches
This problem can be solved using the greedy approach. By greedy, we mean that we simply start cutting the board along every horizontal and vertical line. But this cutting needs to be in a specific manner. Let’s see how we can do this.
- Start by making an integer variable minCost and initialize it to 0.
- Now we talked about cutting the board in a specific manner. This specific manner will involve minimizing the cost of cutting the board.
- To minimize the cost, sort the cost of cutting the horizontal rows in decreasing order.
- Similarly, sort the cost of cutting the vertical columns in decreasing order.
- Maintain two integer variables row_width =1 and column_width =1.
- Make two loop variables i (for rows) and j(for columns). Then run a loop till i < L - 1 and j < W -1.
- Now each time we encounter an edge(in decreasing order), we first check if the rowcost[i] is more than the columncost[j] or not.
- If the row cost is more, then we will be multiplying the rowcost[i] with the current column_width and then add this value to the cost till now. Then increment i and row_width by 1.
- If the column cost is more, then we will be multiplying the columncost[j] with the current row_width and then add this value to the cost till now. Then increment j and column_width by 1.
- Finally, check if any row and column are left, and in case they’re left calculate the cost for these rows and columns.
- Finally return cost, which is our answer.
For example:
L = 3 and W = 3
costL = 1 2 and costW = 2 1
- First, we sort our row and column costs in decreasing order.
- We then choose the highest value from the row costs, i.e 2, and then cut this row. Total cost till now = 2*1 = 2.
- Now we choose the highest costs from column costs, i.e 2 and then we cut 2 such segments. Cost = 2 + 2*2 = 6.
- Then we choose column cost = 1 and cut 2 segments. Cost = 6 + 2*1 = 8.
- Finally, we choose row cost = 1 and cut the final three segments and our cost becomes 8 + 3*1 = 11.
- Hence 11 is our final cost.