Help needed....standard DP,Backtracking Problem

Problem :

This is the time of Christmas and Santa wants to distribute gifts to M children. He has N number of boxes, and each box contains some chocolates. Now, Santa wants to distribute N boxes to M children keeping in mind that distribution should be as fair as possible. To fairly distribute the gift boxes, Santa wants to minimize the maximum number of choclates gifted to a child.

Formally, given M number of children and N boxes, where each box contains some amount of chocolates. The task is to minimize the maximum number of chocolate gifted to a child.

In another word, you have to divide array into M subset such that maximum sum of subset is minimized.

Input:
First line of input contains number of testcases T. For each testcase, there will be three lines of input. First line contains N number of gift boxes, next line contains choclates in each of the N boxes. Last line contains number of children.

Output:
For each testcase, print the minimum number of maximum chocolate a child get.

Constraints:
1 <= T <= 100
1 <= N, M <= 10^6
1 <= A[i] <= 10^8

Example:
Input:
1
4
12 34 67 200
3

Output:
200

Explanation:
Testcase 1: Minimum 200 chocolates will be given to a child which gets the maximum number of chocolate.

Another Corner Case : n = 5 and m=3
array is : [ 3 4 5 5 8]
answer is : 9

how to solve? i didn’t figure out.

2 Likes

It is simple Binary Search

3 Likes

@yaman_47 how simple Binary search? can you explain more?

Sort the array in descending order. Now binary search on the answer. For a particular value check if the array can be divided into subsets with sum not exceeding that particular value.

1 Like

Can your explian how we can check “the array can be divided into subsets with sum not exceeding that particular value” ??

1 Like

You are right. i got your idea. but can you explain more on this statement …
" For a particular value check if the array can be divided into subsets with sum not exceeding that particular value. "
thank you for your reply.

Can you provide the link to the problem ? Just to ensure this is not from an ongoing contest !

1 Like

sure… One of my friend have suggested this question.

Link to Geeksforgeeks courses.
link : https://practice.geeksforgeeks.org/batch/Interview%20Preparation

In, Searching course open contest which will contain this question.
link : https://practice.geeksforgeeks.org/tracks/searching-interview/?batchId=117

here, all courses are for preparation. so, contest is just for practice.

2 Likes

Cool !
You can go through this JAVA code.
Basically what my check function does is to check if I can split the array into number of subsets less or equal to m such that the sum of each subset is <= threshold. So its optimal to choose the value which is just less than threshold value at each step.

Cheers !

2 Likes

You can practice another very similar problem commonly called painters partition problem here

2 Likes

Thanks @drag . can you provide more problemset ?

Thank You @aman_robotics. I got your logic and code. happy coding.

@aman_robotics your logic gives TLE. can you optimize more?
problem link : https://practice.geeksforgeeks.org/contest-problem/santa-and-gift/0/

Well my complexity for check function is O(NlogN), making the total complexity to be O(Nlog^2N), currently I don’t have any idea how to solve it in O(NlogN) or may be less.

1 Like

@aman_robotics it’s ok, thank you for giving your time.

@aman_robotics your logic is wrong, check this case:
1
11
2 2 2 2 2 2 2 2 3 5 12
2

your code gives 19, the correct answer is 18 (5 + 3 + 2 + 2 + 2 + 2 + 2 and 12 + 2 + 2 + 2)

2 Likes

@farmersrice do you have any optimal solution?

Thanks for pointing it out.

1 Like

@sna902055

The problem is NP-complete, it cannot be solved in polynomial time. It can be transformed into the bin packing problem. See this explanation:
https://codeforces.com/blog/entry/67282?#comment-514316

2 Likes

@aman_robotics your code is going to infinite loop.

Long just_smaller = map.floorKey(curr);
if(just_smaller == null){
cnt++;
curr = threshold;
continue;
}
if just_smaller == null, then value of curr is not change,
you assign again,curr = theshoold,
so just_smaller again make null and its infinite loop.

1 Like