NINJA’S BIRTHDAY PARTY

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
9 upvotes
Asked in companies
Dell TechnologiesGoldman SachsNykaa

Problem statement

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.

cakePic

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
6 4
2 1 3 1 4
4 1 2
2 2
2
4

Sample Output 1 :

42
8

Explanation of sample input 1 :

Test Case 1:

In the first line, there is the number of test cases i.e. 2 and in the next line, 6 and 4 are the number of rows and columns of the chocolate following the horizontal costs [2,1,3,1,4] and then the vertical costs [4,1,2]. 
Here, we have started with breaking from the vertical lines that cost 4 and then breaking the two parts from the horizontal line costing 4 and so on.
‘4+(4*2)+ (3*2)+(2*3)+(2*3)+(1*4)+(2*4)’ = ‘42’.

Test Case 2:

Here we have 2*2 sizes of chocolate with horizontal cost 2 and vertical cost as 4. If we first divide it at the horizontal cost then the cost would be ‘2+4*2 = 10’.
While breaking the vertical one first would cost ‘4+2*2 = 8’ 
Hence the answer is 8.

Sample Input 2 :

2
4 4
4 1 3
2 1 6
3 2
2 1
4

Sample output 2 :

33
10
Hint

We would use dynamic programming in this approach i.e. using the previous values for our present solution.

Approaches (2)
Dynamic Programming

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:

  1. We would take a 2d matrix named dp[][] and would initialize ‘i’ = 0, ‘j = 0.
  2. 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]’
  3. We would find the dp[m][n], i.e., the minimum cost of breaking the chocolate into single squares.
  4. 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’)’
  5. The required answer would be 'dp[m][n].'
Time Complexity

O(m*n),  where m and n are the numbers of horizontal and vertical costs.

 

As there are nested loops i.e. there is a loop into another loop, the inner loop would iterate n times for each iteration of the outer loop, hence the time complexity would be O(n^2).

Space Complexity

O(m*n), where m and n are the numbers of horizontal and vertical costs. It is basically the size of the 2d matrix.

 

the space required would depend upon the product of the rows and columns.

Code Solution
(100% EXP penalty)
NINJA’S BIRTHDAY PARTY
Full screen
Console