Break The Board
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

Question

Break The Board

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: OtherExplanation:

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))).

Java (SE 1.8)

/*

	Time Complexity: O(max(L, W) * log(max(L, W)))

	Space Complexity: O(1),



	where L and W is the length and width of the board respectively.

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution 

{



	public static int minimumCost(ArrayList rowCost, ArrayList colCost, int l, int w) 

    {	

        // Sort the costs of row in decreasing order

		Collections.sort(rowCost, Collections.reverseOrder());

		

        // Sort the costs of column in decreasing order

		Collections.sort(colCost, Collections.reverseOrder());

		

        int cost = 0;

        int i = 0;

        int j = 0;

        int rowWidth = 1;

        int columnWidth = 1;

		

        while (i < l - 1 && j < w - 1) 

        {	

            if (rowCost.get(i) > colCost.get(j)) 

            {

				cost = cost + rowCost.get(i) * columnWidth;

				i++;

				rowWidth++;

			}

			else 

            {

				cost = cost + colCost.get(j) * rowWidth;

				j++;

				columnWidth++;

			}

		}



		int rowSum = 0;

		

        // Now running this loop if any row is left

		while (i < l - 1) 

        {

			rowSum = rowSum + rowCost.get(i++);

		}



		// Updating cost

		cost = cost + rowSum * columnWidth;

		int colSum = 0;

		

        // Now running this loop if any column is left

		while (j < w - 1) 

        {

			colSum = colSum + colCost.get(j++);

		}



		// Updating cost

		cost = cost + colSum * rowWidth;



		return cost;

	}



}

Python (3.5)

'''

	Time Complexity: O(max(L, W) * log(max(L, W)))

	Space Complexity: O(1),



	where L and W is the length and width of the board respectively.

'''



def minimumCost(rowCost, colCost, l, w):



	# Sort the costs of row in decreasing order

	rowCost.sort(reverse = True)



	# Sort the costs of column in decreasing order

	colCost.sort(reverse = True)

	

	cost = 0

	i = 0

	j = 0

	rowWidth = 1

	columnWidth = 1

	

	while (i < l - 1 and j < w - 1):

	    

	    if (rowCost[i] > colCost[j]):

	        cost = cost + rowCost[i] * columnWidth

	        i += 1

	        rowWidth += 1

	        

	    else:

	        cost = cost + colCost[j] * rowWidth

	        j += 1

	        columnWidth += 1

	 

	rowSum = 0

	

    # Now running this loop if any row is left

	while (i < l - 1):



		rowSum = rowSum + rowCost[i]

		i += 1

		

	# Updating cost

	cost = cost + rowSum * columnWidth

	colSum = 0

	

    # Now running this loop if any column is left

	while (j < w - 1):



		colSum = colSum + colCost[j]

		j += 1



	# Updating cost

	cost = cost + colSum * rowWidth



	return cost

C++ (g++ 5.4)

/*

	Time Complexity: O(max(L, W) * log(max(L, W)))

	Space Complexity: O(1),



	where L and W is the length and width of the board respectively.

*/



int minimumCost(vector rowCost, vector colCost, int l, int w)

{

	// Sort the costs of row in decreasing order

	sort(rowCost.begin(), rowCost.end(), greater());

	

	// Sort the costs of column in decreasing order

	sort(colCost.begin(), colCost.end(), greater());

	

	int cost = 0; 

	int i = 0; 

	int j = 0; 

	int rowWidth = 1; 

	int columnWidth = 1;

	

	while (i < l - 1 && j < w - 1)

	{

		if (rowCost[i] > colCost[j])

		{

			cost = cost + rowCost[i] * columnWidth;

			i++;

			rowWidth++;

		}

		else

		{

			cost = cost + colCost[j] * rowWidth;

			j++;

			columnWidth++;

		}

	}



	int rowSum = 0;

	

	// Now running this loop if any row is left

	while (i < l - 1)

	{

		rowSum = rowSum + rowCost[i++];

	}



	// Updating cost

	cost = cost + rowSum * columnWidth;

	int colSum = 0;

	

	// Now running this loop if any column is left

	while (j < w - 1)

	{

		colSum = colSum + colCost[j++];

	}



	// Updating cost

	cost = cost + colSum * rowWidth;



	return cost;

}