Help needed....standard DP,Backtracking Problem

help
,
3

It is simple Binary Search

3 Likes
4

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

5

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
6

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

1 Like
7

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.

8

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

1 Like
10

sure… One of my friend have suggested this question.

Link to Geeksforgeeks courses.
link : Practice | GeeksforGeeks | A computer science portal for geeks

In, Searching course open contest which will contain this question.
link : Practice | GeeksforGeeks | A computer science portal for geeks

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

2 Likes
11

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
12

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

2 Likes
13

Thanks @drag . can you provide more problemset ?

14

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

15

@aman_robotics your logic gives TLE. can you optimize more?
problem link : Practice | GeeksforGeeks | A computer science portal for geeks

16

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
17

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

18

@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
19

@farmersrice do you have any optimal solution?

20

Thanks for pointing it out.

1 Like
21

@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:

2 Likes
22

@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
23

Hey, there is problem called as :- Allocate Minimum Number of pages/ Painter Partition Problem(that solution got AC) on GFG in your question.
But that’s wrong, as there is a condition (in Allocate Minimum Number of Pages) that partition must be continous, which is not given for your question(I think moderator might forget to mention that)