Ninja And The Pizzas

Easy
0/40
profile
Contributed by
17 upvotes
Asked in company
Flipkart limited

Problem statement

Ninja loves cooking, and he decided to make the pizza for his friend. His friend loves eating cheese with the pizza; hence Ninja decided to fill the pizza with the cheese.

For our convenience, let's consider the rectangular pizza slices only, and to increase the amount of cheese, the Ninja decided to cut some slices in pizza. Each slice can be cut only once, and the resulting pieces must also be rectangular.

Ninja decided to cut it in at most 'K' slices so that no one gets suspicious.

Given 'N' number of slices have, 'K' maximum number of slices Ninja can cut and two arrays ‘L’ and ‘B’ stating the length and breadth of each slice, your task is to help Ninja find out the maximum extra cheese needed to fill the newly formed boundaries in pizza.

EXAMPLE: 
Input: 'N' = 2, 'K' = 1
       'L' = [4, 2]
       'B' = [6, 8]
Output: 16

To maximize the cheese usage, Ninja can cut a second cake parallel to the side of length 8. So extra cheese needed will be 16.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T', denoting the number of test cases. 

For each test case, the first line contains two integers 'N' number of slices have and 'K' maximum number of slices Ninja can cut. Next, 'N' lines contain two integers, each stating the length and breadth of each slice.
Output format : 
For each test case, print an integer stating the maximum extra cheese needed to fill the newly formed boundaries in pizza.

Output for each test case will be printed in a separate line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= 'T' <= 10
1 <= 'N' <= 10^4
0 <= 'K' <= N
1 <= 'L[i]', 'B[i]' <= 10^4
Time Limit: 1sec
Sample Input 1 :
2
2 1
4 2
6 8
1 1
4 6
Sample Output 1 :
16
12
Explanation Of Sample Input 1 :
For the first test case, to maximize the cheese usage, Ninja can cut a second slice parallel to the side of length 8. So extra cheese needed will be 16.

For the second test case, Ninja can cut the slice parallel to side 6 to get the extra cheese = (40) - (28) = 12
Sample Input 2 :
2
3 2
1 2
3 2
1 3
5 3
2 3
4 5
2 3
2 3
1 2
Sample Output 2 :
12
22
Hint

Try to imagine relations as a graph edge and then try to arrange students (nodes) by their order of visits.

Approaches (1)
Greedy Approach

Approach:  For this problem, we have given 'N' rectangles, and we have to cut 'K' of them parallel to any edge so as to maximize the total sum of the parameters of all the rectangles.

 

Each i-th slice has a length 'L[i]' and breadth 'B[i]'; we can cut it to divide it into two rectangles and maximize the perimeter of that slice.

 

We have to cut it parallel to X[i] = max(L[i], B[i]), and after that, the extra perimeter so formed will be Y[i] = 2 * X[i]. So we will store the extra perimeters given by each cake. After that, sort them and will pick the 'K' maximum cakes from.

 

Algorithm :  

  1. Initialize the variable 'answer'.
  2. Initialize the vector 'X' of size 'N'.
  3. Run a for loop from 0 to 'N - 1' and update each 'X[i]' with maximum of L[i] and B[i].
  4. Sort the array 'X'.
  5. Run a loop from 1 to 'K' and increment 'answer' with 2 * X[n - 1 - i]'.
  6. Return 'answer'.
Time Complexity

O(N * log N)), where 'N' is the size of input arrays 'L' and 'B'

 

As we are sorting the input array and it will take the N * LogN complexity, hence the time complexity will be O(N * LogN)

Space Complexity

O(N), where 'N' is the size of input arrays 'L' and 'B'

 

As we are using extra array 'X' of size 'N' the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Ninja And The Pizzas
Full screen
Console