Last Updated: 11 Dec, 2020
Board Cutting
Moderate
Asked in company
You have been given a flat board of size M * N and you have to cut this board into M * N pieces each of size 1 * 1. To cut the board, you can make only horizontal and vertical cuts.
The cost of cutting horizontal cuts is given by array HORIZONTAL and that of cutting vertical cuts is given by array VERTICAL. The cost is multiplied by the number of segments cut to get the total cost.
Your task is to minimize the overall cost which is the sum of costs of all successive cuts.
For example :
For the board of size 3 * 2 given below, with horizontal = [2] and vertical = [1, 3], the minimum cost of cutting it is explained below:
1st cut: Horizontal cut with cost 3 cutting 1 segment. Cost = 3 * 1.
2nd cut: Vertical cut with cost 2 cutting 2 segments. Cost = 2 * 2.
3rd cut: Horizontal cut with cost 1 cutting 2 segments. Cost = 1 * 2.
Above is the pictorial representation.
Cost = 3 + 4 + 2 = 9.
Note :
As the answer can be large, return your answer modulo 10^9 + 7.
Input format :
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first line of each test case or query contains two space-separated integers 'M' and ‘N’ denoting the number of rows and columns in the board.
The second line contains ‘M-1’ single space-separated integers, representing the costs of cutting Horizontal edges.
The second line contains 'N-1' single space-separated integers, representing the costs of cutting Vertical edges.
Output format :
For each test case, print an integer denoting the minimum possible cost modulo 10^9+7 in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
2 <= M <= 10^3
2 <= N <= 10^3
1 <= horizontal[i] <= 10^9
1 <= vertical[i] <= 10^9
Time limit: 1 sec
Approaches
The idea is to solve the problem with a greedy approach. The total cost will be the sum of C1.S1 + C2.S2 + … C(M + N).S(M + N) where Ci is the cost of cutting a distinct edge and Si is the number of segments present when cutting that particular edge.
Declare two variables, one to store the count of horizontal segments, say ‘hori’ and second to store the count of vertical segments, say ‘verti’. Initialize both with 1.
Now, to achieve the minimum cost, we need to cut the edge with maximum cutting cost first to reduce the total cost, i.e. edge cost * the number of segments.
Here is the algorithm:
- Sort the two arrays ‘horizontal’ and ‘vertical’ in decreasing order.
- Initialize ‘cost’ to 0 which stores the final cost up to a point.
- Take all the edge costs one by one and keep on updating the cost:
- If the current maximum edge cost is horizontal, then, cost = cost + (maxEdgeCost * verti) as ‘verti’ is the number of vertical segments which will get cut.
- Increment ‘hori’ by one as the horizontal segment increases.
- Otherwise, if the maximum edge cost is vertical, then, cost = cost + (maxEdgeCost * hori) as ‘hori’ is the number of horizontal segments which will get cut.
- Increment ‘verti' by one as the vertical segment increases.
- If the current maximum edge cost is horizontal, then, cost = cost + (maxEdgeCost * verti) as ‘verti’ is the number of vertical segments which will get cut.
- Return the calculated ‘cost’.