Break The Waffle
LEVEL:Expert
Description
Charlie wants to divide a big piece of waffle which is made up of m*n square pieces. Each piece is of size 1*1. The shape of waffle is a rectangle of dimension m*n. However, Charlie can break the waffle either horizontally or vertically, along the lines such that the square pieces are not destroyed.
Each break along a line has a certain cost associated with it. The cost is only dependent on the line along which the waffle is being broken, and not on its length.
The total cost is obtained by summing up the costs of all the breaks.
Given the cost associated with each line, Charlie wants to know the minimum cost of breaking the waffle into single square pieces.
Input Format
First line contains two integers m and n denoting the number of rows and columns, respectively.
This is followed by m-1, each line contains an integer denoting the cost of breaking a waffle along a horizontal line.
This is followed by n-1, each line contains an integer denoting the cost of breaking a waffle along a vertical line.
Constraints
1<=n<=10^5
1<=m<=10^5
Output Format
Output should be a single line integer denoting the minimum cost to break the waffle into single square pieces.
2 2 3 4
10
6 4 2 1 3 1 4 4 1 2
42
8 8 2 1 3 1 4 8 9 4 1 2 7 5 6 3
179
Login to see Discussion
Approach
Approach:
Step-1: Group the given costs with their respective dimensions as tuples, example: (cost,"h") or (cost, "v"), to identify the cost uniquely.
Step-2: Append all these tuples to list and sort it.
Step-3: Initialize two variables, X and Y to 1 and totalCost to 0.
Step-4: If length of list is greater than 0, pop the lost the tuple and store in another varible as 'p'
Step-5: If dimension is h, increment X with 1 and totalCost as totalCost+ cost * Y (until now there are Y vertical blocks)
Step-6: If dimension is v, increment Y with 1 and totalCost as totalCost+ cost * X (until now there are X vertical blocks)
Step-7: Repeat Step-4 until it breaks the condition.
Step-8: Print the result
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution