Just realized DP is applicable here. Great explanation. Please make videos on questions where DP is not optimal but can solve it. It will help understand the concept better.
this question is example of that. DP is not optimal as it takes O(n2) . whereas, with the binary search approach you can solve this question in O(nlogn). so in this question, DP is not optimal but it can solve it.
Yes binary search is more efficient here , but greedy problems are hard to prove and come up with intuition whereas for me DP problems are real use of computer and programming where most of work is on computer and you just apply a n optimised Brute force that is DP, quick to come up with solution later one can ponder upon further methods
if you are teaching , then what hard difficulty or insane difficulty or impossible one 😂😂😂😂😂😂😂😂 every solution seems super simple and super easy❤❤❤ one request............ can you make dsa cracker sheet like that of love babbar's or striver's according to your priorities?? it will be very helpful😅😅😅
I am making topicwise course on each data structure and algo topic. At the end of the DSA course, you will get a very good DSA sheet with all the videos explained :) That will be better than just providing problem name.
@@priyanshubharti5198 This might help : public class Solution { static int MOD = 10000007; public boolean isValid(ArrayList C, int painters, int mid){ int sum = 0; int len = C.size(); int actual = 1; int i = 0; while(i < len){ sum = (sum%MOD + C.get(i)%MOD)%MOD; if(sum > mid){ actual++; sum = C.get(i)%MOD; } i++; } return (painters >= actual); } public int paint(int painters, ArrayList C) { int len = C.size(); int start = 0; int end = 0; for(int i = 0; i < len; i++){ start = Math.max(start%MOD, C.get(i)%MOD); end = (end%MOD + C.get(i)%MOD)%MOD; } int ans = -1; while(start
I think if you apply discrete binary search with lower bound of search space as 60 and upper bound of search space as 10+40+60+30 and do a binary search it'll improve the time complexity
I may be wrong but please hear me out, what if we calculate the total array value (say it' 150, and k =3,) so we just traverse the array are the moment cumulative sum reaches >= 50 (150/3)we declare a partition, given that the num of array element left is higher than painter lefts , and if they're equal, just partition there so no one remains idle. Can anyone tell me if this is wrong, seem to work for some problems.
case where we are partitioning at last of the array i.e for 2 painter - one painter get all elements and second painter gets nothing. we can ignore this case right? As above calculation will never lead to optimal soln.
In maximum pages problem the array should be sorted....but for the binary search methos of painters partition problem why the array need not to be sorted....please reply
It is intuitive. When you have multiple branching at a node then you use loop otherwise you will have to write one line for each branching which will be cumbersome.
Can we divide the sum/3 and after getting the the here it is around 66 and we start adding the number from the beginning and putting the partition after getting a number more than the average (70) Then the complexity would be O(n) Please comment if it is acceptable Thanks for making these videos,are really helpful
Just take the first example that you have given 10,30,60,10,40 Sum =150 Average=150/3(painters)=50 Now from the beginning ,if we start dividing the values in a manner,so that the sub array has a value close to 50 We will get 10,30|60|10,40 Same with the another array given by you 10,40,20,30,40,50 AVG=67 And if we do the partition,we will get 70 as the max value.
How do we solve it if time taken by each painter differs from other painters. Like one painter paints it [10,20,30 ,40] and other painter in [5,5,40,50] and then minimize total time taken ?
Thank you. This is well explained. I stll have one question though: in the DP approach, why at each time we only look at DP[ i- 1 ][*], is it because we are only considering for this specific patiner i, and all answer to previous painters are stored in the DP table ?
Let us say the cur partn (or painter) divides the domain into LHS and RHS. LHS is solution to a sub-problem with all elements upto cur partn with one less partn. RHS is cur partn (which is sum of all elem in this cur partn). And all LHS is stored in DP table for all increasing number of partns and all increasing number of elements. LHS + RHS = total solution, LHS = count of partn - 1, RHS = 1 partn, so LHS+RHS = count of partn - 1 + 1 = count of partn
The backtracking part for why they were returning the minimum was tough to understand coz we need the max like max(x,y,z) is max(x,max(y,z) so we should be returning max(y,z) but wer were returning min(max(y1,z1), max(y2,z2).......max(yi,zi)) but this equation is also simple to understand as both will be same when you chq the results, the intuition also is smart!
There is no point in solving something from left if you already found it from right. Right and left doesn't matter. What matters ia that you understand the algo. Then you can apply any direction according to your wish.
Was looking for a Binary search solution was surprised to see this DP approach, goes to show how a single problem can be solved in so many ways
True :)
But what abt time complexity?nlogn is way better than n2.
@@RAJPATEL-nm9nz we are just learning how to solve a problem in different ways
binary search for higher values of K is a bit tricky
Just realized DP is applicable here. Great explanation. Please make videos on questions where DP is not optimal but can solve it. It will help understand the concept better.
Yea sure
this question is example of that.
DP is not optimal as it takes O(n2) . whereas, with the binary search approach you can solve this question in O(nlogn).
so in this question, DP is not optimal but it can solve it.
This can be done using binaru search as well... It is similar to allocating pages problem
Yes
Thanks. This is very well explained. I'll go search for your "AGGRESSIVE COW SPOJ" problem to see how to use binary search to do this problem.
Thanks bhai . I was able to solve it with binary search but came here to see dp solution because i was having some confusion in that
Welcome :)
Hey @Aman rai , bro can you share your binary search solution because I am not able to solve this Q with binary search...
@@priyanshubharti5198 bro solved it few months back not remember now.
@@amanrai8010 bro what's your username in codechef/codeforces/interviewbit?
@@priyanshubharti5198 bro i don't do codechef. I am on leetcode. Connect me on LinkedIn
Yes binary search is more efficient here , but greedy problems are hard to prove and come up with intuition whereas for me DP problems are real use of computer and programming where most of work is on computer and you just apply a n optimised Brute force that is DP, quick to come up with solution later one can ponder upon further methods
sir you are doing a great job
Thanq :)
very good explanation. Thank you!
Longest valid Parentheses can u please make a video on this. your videos are really helpful. stuck in this problem
Will add this in my to-do problem list :)
if you are teaching , then what hard difficulty or insane difficulty or impossible one 😂😂😂😂😂😂😂😂
every solution seems super simple and super easy❤❤❤
one request............ can you make dsa cracker sheet like that of love babbar's or striver's according to your priorities??
it will be very helpful😅😅😅
I am making topicwise course on each data structure and algo topic. At the end of the DSA course, you will get a very good DSA sheet with all the videos explained :) That will be better than just providing problem name.
@@techdose4u ok , as you wish😅😅
I was saying just to cover all those requied to crack dream companies👍👍
with binary search, this problem will fall in an intermediate category not hard !! right?
Right
Hey @Sanjay Joshi, bro can you share your binary search solution because I am not able to solve this Q with binary search...
@@priyanshubharti5198 This might help :
public class Solution {
static int MOD = 10000007;
public boolean isValid(ArrayList C, int painters, int mid){
int sum = 0;
int len = C.size();
int actual = 1;
int i = 0;
while(i < len){
sum = (sum%MOD + C.get(i)%MOD)%MOD;
if(sum > mid){
actual++;
sum = C.get(i)%MOD;
}
i++;
}
return (painters >= actual);
}
public int paint(int painters, ArrayList C) {
int len = C.size();
int start = 0;
int end = 0;
for(int i = 0; i < len; i++){
start = Math.max(start%MOD, C.get(i)%MOD);
end = (end%MOD + C.get(i)%MOD)%MOD;
}
int ans = -1;
while(start
@@uditagrawal6603 thanks man🔥🔥
Amazing explanation . Very very clear.
Thanks :)
I think if you apply discrete binary search with lower bound of search space as 60 and upper bound of search space as 10+40+60+30 and do a binary search it'll improve the time complexity
Yes that is offcourse better. People were asking for DP soln 😅 I have already explained discrete binary search in AGGRESSIVE COW SPOJ problem.
Naah its actually cool coz I didn't have the DP approach, I am glad you did it sir with DP
😅 thanks
Well explained sir!! Thanks
Welcome :)
Nice explanation,u got a new subscriber
Thanks :)
I may be wrong but please hear me out, what if we calculate the total array value (say it' 150, and k =3,) so we just traverse the array are the moment cumulative sum reaches >= 50 (150/3)we declare a partition, given that the num of array element left is higher than painter lefts , and if they're equal, just partition there so no one remains idle.
Can anyone tell me if this is wrong, seem to work for some problems.
case where we are partitioning at last of the array i.e for 2 painter - one painter get all elements and second painter gets nothing. we can ignore this case right?
As above calculation will never lead to optimal soln.
awesome explanation sir
In maximum pages problem the array should be sorted....but for the binary search methos of painters partition problem why the array need not to be sorted....please reply
I will go through binary search for this problem and then give your reply.
It's same as pages allocation right?
Right
@@techdose4u thanks for reply dude!
Sir can u plz tell us that when to call recursive function in loop or not it so confusing 🙏
It is intuitive. When you have multiple branching at a node then you use loop otherwise you will have to write one line for each branching which will be cumbersome.
TECH DOSE thank you sir
Welcome
why did we run the loop till 1 only?
Sir this code is actually giving segmentation fault in gfg
Please try with new code from gfg or try to implement yourself. You will get it
Can we divide the sum/3 and after getting the the here it is around 66
and we start adding the number from the beginning and putting the partition after getting a number more than the average (70)
Then the complexity would be O(n)
Please comment if it is acceptable
Thanks for making these videos,are really helpful
I actually did not understand your algo. Please clarify it with example.
Just take the first example that you have given
10,30,60,10,40
Sum =150
Average=150/3(painters)=50
Now from the beginning ,if we start dividing the values in a manner,so that the sub array has a value close to 50
We will get 10,30|60|10,40
Same with the another array given by you
10,40,20,30,40,50
AVG=67
And if we do the partition,we will get 70 as the max value.
How do we solve it if time taken by each painter differs from other painters. Like one painter paints it [10,20,30 ,40] and other painter in [5,5,40,50] and then minimize total time taken ?
also upload a solution using binary search
The approach is good but how do we do it when the constraints of n & k are of order 10^5
Thank you. This is well explained. I stll have one question though: in the DP approach, why at each time we only look at DP[ i- 1 ][*], is it because we are only considering for this specific patiner i, and all answer to previous painters are stored in the DP table ?
Let us say the cur partn (or painter) divides the domain into LHS and RHS. LHS is solution to a sub-problem with all elements upto cur partn with one less partn. RHS is cur partn (which is sum of all elem in this cur partn). And all LHS is stored in DP table for all increasing number of partns and all increasing number of elements.
LHS + RHS = total solution,
LHS = count of partn - 1,
RHS = 1 partn,
so LHS+RHS = count of partn - 1 + 1 = count of partn
Sir, please make a video to solve this problem using Binary Search.
Sir , can you make video on count number of sub-arrays having equal number of zeros and ones !!
Will add this to my to-do list :)
@@techdose4u thank you sir :)
I didn't understand that Backtracking approach, I need help!
😅Bro. Did you understand DP? If you did then backtracking is much more simpler.
The backtracking part for why they were returning the minimum was tough to understand coz we need the max like max(x,y,z) is max(x,max(y,z) so we should be returning max(y,z) but wer were returning min(max(y1,z1), max(y2,z2).......max(yi,zi)) but this equation is also simple to understand as both will be same when you chq the results, the intuition also is smart!
Nice explanation! Is the DP approach top down or bottom up? I thought it was top down but the git code says bottom up?
it should be sum(arr,p,j-1) instead of sum(arr,p,j);
itna maza kyun aa raha haiiii
I guess binary search solution is more efficient
Yes...I just explained it for the purpose of DP.
It could have been better if u solved from left , and not just explaining geeks for geeks article
There is no point in solving something from left if you already found it from right. Right and left doesn't matter. What matters ia that you understand the algo. Then you can apply any direction according to your wish.