Divide Chocolates

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
27 upvotes
Asked in companies
VisaJosh Technology GroupKellton Tech Solutions Limited

Problem statement

Ninja bought chocolate consisting of some chunks. The sweetness of each chunk is given in an array ‘ARR’. Ninja has ‘K’ friends, and he wishes to divide the chocolate into 'K' + 1 cut with some consecutive chunks. He wants to divide the chocolate into chunks under the condition that he will take the piece that has the minimum total sweetness.

He is very busy doing other stuff. Can you help him to maximize the total sweetness of the part that you will get under the given condition?

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. Then the test cases follow.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the size of array ‘ARR’ and the number of friends Ninja has.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array ‘ARR’.
Output Format: 
For each test case, print the maximum sweetness that Ninja can get under the given condition.

Print the output of each test case in a new line.
Note: 
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints: 
1<= T <= 10
1 <= N <= 50000
0 <= K < N
1 <= ARR[i] <= 10000

Where 'ARR[i]' is the sweetness of the ‘i_th' chunk.

Time Limit: 1 sec
Sample Input 1:
2
9 3
5 6 7 8 9 10 11 12 13
3 2
2 2 2
Sample Output 1:
17
2
Explanation for Sample Input 1:
In the first test case, the sweetness of the chunks are [5, 6, 7, 8, 9, 10, 11, 12, 13] and Ninja has 3 friends. So, it is to be divided among 4 people including Ninja himself. In order to maximize the total sweetness of Ninja, one possible division is [5, 6, 7], [8, 9], [10, 11], [12, 13]. The minimum sweetness of one part is 17. So, the answer is 17.

In the second test case, the sweetness of the chunks are [2, 2, 2] and Ninja has 2 friends. So, it is to be divided among 3 people, and there are only 3 chunks. So, all three friends will be getting one chunk each. So, the total sweetness that Ninja will get is 2. So, the answer is 2.
Sample Input 2:
2
3 2
5 6 7
10 4
2 3 2 3 2 3 2 3 2 3
Sample Output 2:
5
5
Hint

Iterate through every possible value of sweetness that you can have? Try to ignore the subproblems using DP.

Approaches (2)
Dynamic Programming

The idea is to figure out the recursive calls and optimize them using dynamic programming.

It breaks down into a problem of dividing the array into ‘K’ + 1 partitions such that the partition which has the lowest sum of sweetness is maximum as compared to all the possible partitions. It’s better to make a prefix array as we would need the prefix sum of the array in every iteration. 

Now, we will start from the bottom, and then we will find the final answer. We will find the answer for breaking the subarray from indices from 0 to ‘i’ into ‘j’ parts where ‘i’ lies from 0 to ‘N’ - 1 and ‘j’ lies from 0 to a minimum of ‘M’ and ‘i’ + 1.

There is a base condition: If the number of chunks is less than the number of desired divisions, then Ninja won’t get any chunks. So, the answer will be 0.

 

The steps are as follows:

 

  • Base Condition: If ‘K’ is greater than or equal to the number of chunks in the array ‘ARR’, return 0.
  • Increment ‘K’ by 1 as there are ‘K’ friends and the number of partitions expected is ‘K’ + 1.
  • Calculate the prefix sum of the given array and store it in an array ‘PREFIXSUM’ as we will require it in every iteration. Otherwise, it will increase the time complexity.
  • Initialize a matrix ‘DP’ with the number of rows = ‘N’ and the number of columns = ‘K’ + 1 to the minimum integer value. In this matrix ‘DP[i][j]’ stores the sweetness of the part whose sum of sweetness is minimum after dividing the subarray from indices 0 to ‘i’ into ‘j’ parts. So, for any ‘i’, the 0'th part is not used for all ‘i’ in the range 0 to ‘N’ - 1.
  • Iterate from ‘i’ = 0 to ‘N’ - 1 and fill the first column with the prefix sum of the respective indices.
  • Iterate from ‘i’ = 1 to ‘N’ - 1:
    • Iterate from ‘j’ = 2 to a minimum of ‘K’ and ‘i’ + 1:
      • Now, we will break the subarray from indices ‘0’ to ‘l’ into ‘j’ - 1 part and then ‘l’ + 1 to ‘i’ into 1 part for all ‘l’ in the range 0 to ‘i’ - 1.
      • Iterate from ‘l’ = 0 to ‘i’ - 1:
        • Store the value of prefix sum from ‘l’ + 1 to ‘i’ + 1 in a variable ‘TEMP’.
        • Update the value of ‘TEMP’ to the minimum of ‘TEMP’ and 'DP[l][j-1]'.
        • Update the value of ‘DP[i][j]’ to the maximum of ‘DP[i][j]’ and ‘TEMP’.
  • Return ‘DP[N-1][M]’ as the final answer as this is the answer for breaking the array arr from 0 to ‘N’ - 1 into ‘M’ parts.
Time Complexity

O((N^2)*K),  where ‘K’ denotes the number of friends and ‘N’ is the number of chunks.

 

As we are iterating over all the elements and then creating all possible divisions from 2 to ‘K’ and then choosing the maximum answer from all the possible divisions from 0 to ‘i’ - 1. Hence, the overall time complexity is O((N^2)*K).

Space Complexity

O(N*K), where K denotes the number of friends and N is the number of chunks.

 

As we are using a 2D matrix of size N*(K+1) to store the results for breaking the subarray from indices 0 to n - 1 into K parts. Hence, the overall space complexity is O(N*K).

Code Solution
(100% EXP penalty)
Divide Chocolates
Full screen
Console