Break The Board

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.

Start by cutting the vertical column with cost = 2, hence cost becomes 2. Then make two cuts at the horizontal row with the cost = 2, Cost = 2*2 + 2 =6. Then vertically cut two columns with cost = 2, Cost = 6 + 1*2 = 8. Finally make three horizontal cuts with cost = 1. Final cost becomes 8 + 1*3 = 11.

In this case, we’ll be doing a total of 2 cuts. In the first cut, we’ll be cutting the first segment and our cost will now be 1*2 = 2 and in the second and the final cut, we’ll be cutting 2 segments each of cost one. Hence our final cost be 2 + 2*1 = 4.

Greedy Approach

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.

Time Complexity

O(max(L, W) * log(max(L, W))), where L and W are the length and width of the board respectively.

The Time Complexity to sort the cost of the horizontal cut is O(L * log(L)). The Time Complexity to sort the cost of the vertical cut is O(W * log(W)). Hence, the overall Time Complexity is O(max(L, W) * log(max(L, W))).

Space Complexity

O(1).

Constant space is being used. Hence, the overall Space Complexity is O(1).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of Sample Input 1:

Sample Input 2:

Sample Output 2:

Explanation of Sample Input 2: