Last Updated: 18 Feb, 2021
NINJA’S BIRTHDAY PARTY
Moderate
Asked in companies
Ninja and his friends went to a restaurant on the occasion of Ninja’s birthday. There he was offered by his friends to do some task, if he wins, he would not have to pay a single penny, his friends would pay instead of him. But if he loses, he would have to pay the whole bill. The task was that he was given a bar of chocolate and was asked to break it into single squares.
The rules were as follows:
1.Parts of the chocolate may be broken along the vertical and horizontal lines as indicated by the broken lines in the picture.
2.Each break of a part of the chocolate is charged a cost expressed by a positive integer.
3.This cost does not depend on the size of the part that is being broken but only depends on the line the break goes along.
4.Denoting the costs of breaking along consecutive vertical lines with x1, x2, ..., xm-1 and along horizontal lines with y1, y2, ..., yn-1.
5.The cost of breaking the whole bar into single squares is the sum of the successive breaks.
Now, Ninja has to break the chocolate in such a way that results in minimum cost. So your task is to find the minimum cost.
Input Format :
The first line of input contains ‘T’ number of test cases.
The first line of each test case contains, input ‘m’ and ‘n’ i.e. a number of rows and columns.
The second line of each test contains ‘m-1’ space-separated integer which denotes the horizontal cost.
The third line of each test contains ‘n-1’ space-separated integer which denotes the vertical cost.
Output Format :
For each test case return the minimum cost to breaking the chocolate into a single square.
Note :
You do not need to print anything.It has been already taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= Xi <= 100
1 <= Yi <= 100
2 <= m,n <= 1000
Where ‘T’ represents the number of test cases, ‘x[i]’ represents the horizontal cost at ‘i-th’ index, ‘y[i]’ represents the vertical cost at ‘i-th’ index, ‘m’ is a number of rows and ‘n’ is a number of columns.
Time Limit: 1 second
Approaches
We would use dynamic programming in this approach, i.e., using our present solution's previous values.
Approach:
In this approach, we would take a 2d matrix and would make use of previously stored values.
The algorithm will be:
- We would take a 2d matrix named dp[][] and would initialize ‘i’ = 0, ‘j = 0.
- We would fill the matrix according to the following steps:
- The horizontal part would be filled as:
- ‘dp[i][0]’= ‘x[i]’+ ‘dp[i-1][0]’
- The vertical part would be solved as:
- ‘dp[0][j]’= ‘y[i]’+ ‘dp[0][j-1]’
- The horizontal part would be filled as:
- We would find the dp[m][n], i.e., the minimum cost of breaking the chocolate into single squares.
- By storing the values in two variables t1 and t2, check which is smaller and store it into the dp matrix's respective indices and then print the dp[m][n].
- ‘t1’ = ‘dp[i-1][j]’ + ‘x[i]’ * ‘(j+1)’
- ‘t2’ = ‘dp[‘i’][‘j’ - 1]’ + ‘y[‘j’]’ * ( i’ + 1)’
- ‘dp[i][j]’ = ‘min(‘t1’, ‘t2’)’
- The required answer would be 'dp[m][n].'
The number of cuts required is always the same.
Proof:
C(rows, cols) = rows + cols + rows * cols
C(0, 0) = 0 (a single box chocolate needs 0 cut)
Cut horizontally:
C(cols, rows) = 1 + C(a, rows) + C(b, rows) such that a + b + 1 = n.
C(cols, rows) = 1 + a + rows + a * rows + b + rows + b * rows.
= 1 + ( n - 1 ) + 2 * rows + ( cols - 1 ) * rows
= cols + rows + cols * rows.
Equally for the vertical cuts.
The problem is similar to the weight distribution problem, and each cut will happen sooner or later. The "weight" of a cut is increasing, and if a vertical and horizontal cost is equal, cutting order does not matter. So we greedily choose the largest cut-cost each time.
The algorithm will be:
- Firstly, sort both the horizontal and vertical costs in decreasing order.
- Now, we will check the sequence of breaking the parts of the chocolate for minimum cost.
- At first, we will initialize ‘i’=0,’j’=0,’h’=1,’v’=1 where h and v are the horizontal and vertical parts count and sum=0, i.e., the minimum cost.
- We will start a loop,checking the condition [‘i’ < ‘m’ & ‘j’ < ’n’]:
- We will determine whether the horizontal cost is greater or the vertical one.
- The one with greater value is breaking the chocolate; hence it will be added to the sum after being multiplied by the number of pieces.
- If ‘x[i]’ > ‘y[j]’ :
- ‘ans’ += ‘x[i]’*’v’
- ++’h’
- ++’i’
- Else
- ‘ans’ += ‘y[j]’*’h’
- ++’v’
- ++’j’
- We will check whether we have traversed all the costs or not, i.e., if the chocolate is still yet to be broken into single squares.
- If some horizontal costs are left out, then add them to the sum:
- ‘sum’ += ‘ans’ * ‘v’ [initially ‘ans’ = 0]
- Similar steps would be taken in case of vertical costs:
- ‘sum’ += ‘ans’ * ‘h’ [initially ‘ans’ = 0]
- Now, the ‘sum’ will be our final answer.