Last Updated: 10 Dec, 2020
Chocolate Bar
Hard
Asked in company
You are given a chocolate bar in the form of a grid consisting of N x M pieces of chocolate. Your task is to take out exactly ‘K’ pieces of chocolate by cutting the chocolate bar either horizontally or vertically. This operation will cost you the square of break length.
For example: If you have a chocolate bar of size 3x4, then you can cut horizontally and get two bars of the chocolate of size 1x4 and 2x4. The cost of this cut will be 4^2 = 16 or you can cut vertically and get two bars of the chocolate of size 3x1 and 3x3. The cost of this cut will be 3^2 = 9.
You are given ‘Q’ queries and for each query you need to find the minimum cost such that after all the cutting operations, exactly ‘K’ pieces are obtained from a chocolate of dimension N x M.
Note:
1.You can discard the remaining N x M - K pieces.
2.You do not need to print anything. It has already been taken care of by our driver code. Just implement the given function and return the minimum cost of cutting the chocolate bar to get exactly ‘K’ pieces of chocolate for each query.
Input Format:
The first line of the input contains an integer ‘Q’ denoting the number of queries.
The first line of each query contains three space-separated integer values ‘N’, ‘M’, ‘K’ denoting the dimensions of the chocolate bar and the number of pieces you want, respectively.
Output Format:
You need to print ‘Q’ lines, each line contains the output of each query which is an integer denoting the minimum total cost needed to break the chocolate bar, to make it possible to have K pieces of chocolate.
Constraints:
1 <= Q <= 10^4
1 <= N,M <= 30
1<= K <= min(NxM,50)
Time Limit: 1 sec
Approaches
- We will break our problem into subproblems and solve each subproblem using recursion.
- If initially, we are given the bar of ‘N’x’M’ dimension then we can try all possibilities of cutting this bar into smaller bars to get ‘K’ pieces. For example, we can break this bar into two bars of dimensions (‘i’ x ‘M’), (‘N-i’ x ‘M’) if we cut horizontally where 1<= ‘i’<’ N’ or in the dimensions of (‘N’ x ‘j’), (‘N, ’j’-’M’) if we cut it vertically where 1<=’j’< ’M’ and then recursively solve this problem for each bar in the same way.
- After cutting a bar into two smaller bars we choose both the bars one by one to get exactly ‘K’ pieces of chocolate.
- For each bar, we have two options.
1. If the total pieces present in the current bar is greater than equal to ‘K’, then we will further try to break this bar.
2. If the total pieces present in the current bar is less than equal to 'K’, then we keep them and follow the same procedure for the remaining pieces out of K. Let’s say the pieces will be X where X <= K then we follow the same process for the remaining K-X pieces. - We add the square of side length to our answer at each step of cutting.
- Finally, we will take the minimum cost of getting ‘K’ pieces from both the bars.
- If we draw the recursion tree of the above recursive approach, then we can observe that it has overlapping subproblems. Thus, we can use Dynamic programming to memoize our states.
- Definition: dp[n][m][k] will store the minimum cost of cutting total k pieces from n x m chocolate bar.
- Transitions:
1. Let our function be f(n,m,k) then we try all possibilities by cutting the bar horizontally at each ith row, where ‘i’ varies from 1 to ‘n-1’. At each cut, we will get 2 bars of dimensions ( i x m ) and (n-i x m) with the cost of cutting equal to ‘m’*’m’ ( side of length will be ‘m’ when cut horizontally).
2. Now for each of the two bars, we have two choices either take all pieces of one bar and cut the other bar for the remaining pieces, or don’t take the pieces at all and cut the same bar again to get the required pieces. thus the transitions will be f(n-i,m,k - i*m) and f(i,m,k) respectively.
3. We take the min of the cost which we will be getting from the above two choices, i.e., m*m + min( f(i, m, k), f(n-i, m, k-i*m) ) for all ‘i’ where ‘i’ varies from 1 <i<n.
4. We repeat the above procedure for the case cutting vertically also.
5. The transitions for cutting vertically will be n*n + min( f(n,j,k) , f(n,m-j,k-j*n) ) for all ‘j’ where ‘i’ varies from 1 <j<m. - Base case: if our ‘K’ is zero or ‘K’ is equal to the size of bar then in that we don’t need to make any cuts and we return zero as our answer.
- Finally, the overall minimum which we got by cutting horizontally or vertically will be our final answer.
- We will create a 3 dimensional DP table lets say DP[n][m][k] for storing the current row, column and number of chocolate required respectively.
- Definition: DP[n][m][k] will be storing the minimum cost to take exactly k chocolates out of a chocolate bar consisting of n rows and m columns.
- Transitions: At each stage, we will have two options:-
1. Keep all the pieces of the current bar if the pieces are less than or equal to our need. Then the transition state will be DP[n-i][m][k-i*m] (if we try to cut horizontally at ith row) + m*m ( cost of cutting horizontally ).
2. If the pieces are greater than or equal to our need then we don’t include them now and further try to break them in smaller pieces. Then the transition state will be DP[n-i][m][k] (if we try to cut horizontally at ith row) + m*m ( cost of cutting horizontally ).
3. The minimum of all possibilities of trying cutting horizontally or vertically will be our answer for each state. - Base case: If K = 0 or K = N*M i.e, K is equal to the size of the bar in these two cases we don’t need to cut the bar and our answer will be zero.