 # 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]

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. "

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.

In, Searching course open contest which will contain this question.

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?

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