DP with Bitmasking #1
Vložit
- čas přidán 28. 08. 2024
- Since we already know what bitmasking is, so let us get started with DP with bitmasking.
Incase you want to learn about bitmasking first then you can watch: • What is Bitmasking
I will discuss the brute force solution followed by recursive solution followed by the DP solution and then code it explaining my thought process line by line.
Problem statement: docs.google.co...
Solution: ideone.com/FRrbFB
Make sure you subscribe and if need more reasons apart from the easy to understand explanation to tough concepts then you can watch: m.facebook.com...
Enjoy watching!!
Super useful books for algo ds and programming fundamentals!
1. Introduction to Algorithms by Cormen: amzn.to/35AmQqu
2. The Algorithm Design Manual: amzn.to/2K9RGPq
3. Fundamentals of Data Structures in C++: amzn.to/2LCwIsN
4. Object-Oriented Programming by E Balagurusamy: amzn.to/2Xxmdtr
5. Head First Java: amzn.to/39kb44K
6. Cracking the coding interview: amzn.to/3iDOHLK
7. Database System concepts: amzn.to/3pisuFQ
8. Operating Systems: amzn.to/39fcmis
9. Discrete Mathematics: amzn.to/2MlgCE6
10. Compiler Design: amzn.to/3pkYvx2
You are blessed with great teaching skills. Please don't stop posting videos.
Thanks Tarun :)
That sublime text is somehow a magical platform, everytime you make a compilation error, you open it and it magically tells you immediately what was the error in your code🤣. BTW very nice video.
Sublime sure is magical
I open sublime and instantly it tells me the error in my code
Top Tip for debugging your codes xD
Text Summary for Video :
J1,J2,J3 ... Jn Jobs
P1,P2,p3.... Pn People
Assign Job to P1 in N ways
Assign Job to P2 in N - 1 ways
Assign Job to P3 in N - 2 ways
.. so on
Time Complexity = N * (N - 1) * (N - 2)...* 1 = O(N!)
1. Idea - Recursion
(CurJobToAssigned,PeopleSet) = ({1..N},{P1,P2..PN})
(1,{P1,P2..PN})
/ \
(2,{P2,P3..PN}) ... (2,{P1,P3...PN})
-> Obviously This recursion would have overlapping states.
-> Considering Each permutation as a state and storing it would be heavy storage intensive task
-> Seeing the constraints what if we represent each permutation of set through a integer.
2. Defining DP
DP[i][mask] = where mask is integer representation of a permutation of a subset given.
= Min cost of assigned given people by mask to i to N jobs remaining.
3. Recurrence
dp(i,mask) = MIN { for all valid j | { C(j,i) + dp(i + 1,mask with jth bit off) } }
Time -> O(N^2 * 2^N)
Space -> O(N * 2^N)
Great
This is also known as Assignment problem in Optimization technique mathematics. Fun to see it solve with dp with bitmasking :)
Yess, infact there is an Algorithm known as Hungarian Algorithm to solve this problem which is more efficient than the DP bitmask solution.
The Problem looked great for an introductory video on bitmask dp :)
@@AlgosWithKartik can you please make a video on hungarian algorithm too?
NO.1 youtube channel for CP topics...
Please make more videos quickly...
Thanks bro for keeping my request.Keep up the good work .Will share your channel to my friends.
Thanks Akash!
Your way of explaining things is really good, Thanks for the awesome explanation.
The last seconds of video was really important because i knew already that your earlier code is going to fail due to mistakes you made. I mean, everyone makes mistakes, so just chill. I am not complaining 😅☺
i understands your solution in 15 min...but took 20 min to think the time complexity.
overall one of the great explanation
Rare + gem 💎 content .... Thanks bhaiya 👍
Really great video brother. Appreciate your teaching skills 🙌
really helpful video
Dp(i,mask) is not required coz set bits of mask = i hence i is redundant.
Dp(mask) would do
TC - N*2^N
SC - 2^N
Did I not mention this anywhere in the entire video? xD
Anyway the observation is correct :)
Tried to keep it as beginner friendly as possible.
Also based upon this do you think I'm correct if I establish a tighter bound on my Implementation and say that it is O(N*2^N) in the worst case?
@@AlgosWithKartik yes that is true but space would be reduced if we dont use i
Genuine padhaya bhaiya
Bahut badhiya sir ❤❤
really good explaination skills very clear and crisp
Damn , such a smooth explanation ! Loved it and thank you !
Very clear and detailed explanations!
Thanks for your help fellow DTUite!
Great man. I just solved a problem using this concept.. Very clear explanation. Thanks a lot
really nice explanation.
Thanks a lot
Tum bhut mast kaam krta hai Kartik bhai
Thanks a ton for the wonderful explanation...i am very grateful
It's great explanation. But I am little bit confused about time complexity.
Claim : the number of unique states are just 2^n.
Explanation :
here we have two dp states, the job number and mask. But the job number is nothing but the number of off bits in mask. So, it's a redundant dp state. So, unique state is 2^n only.
Like
for i = 0, mas which has zero set bit is only valid mask, nC0 = 1
For i=1, mask which has only one set bit are only valid masks, so nC1 masks
.....
For i=n, possible masks are nCn.
And since 0
Awesome series bhaiya🤩🤩
Thanks for the content . I like the way you explain the things.
You are brilliant at teaching!
Time complexity can be optimized to O(n×2^n) as given the bitmask j, we can easily find out state i as it is the number of 0s + 1, hence we won't need a 2D dp.
best series!!!
Nice one ... enjoyed learning this part.
Thank you so much sir.... Awesome explaination😄
Very well explained!
super super super....awsm explanation!!!!
bro once again thanks for such a beautiful lecture
Really a valuable content
Helpful, Thanks!
this video was greatfuly helpful sir, thanks in advance. Is it possible for you to make video about number of wonderful substring problem from leetcode please ?
Thanks bro but I have a doubt here,since the paths will always be unique so I think dp[mask] is enough instead of dp[state][mask],right?
by using the number of set/unset bits in the mask we can uniquely identify the correct value for 'state'.
So yes you are correct 'state' here is redundant and we can have solution with/with-out it.
@@AlgosWithKartik thank you so much for your instant reply bro,a lot of youtubers don't reply to our doubts but you are awesome bro.Thank you so much once again.
Good explanation!
Really good explanation!
Hi Kartik,
I've seen your video on calculating the time and space complexity for dp problems but i'm not fully convinced that the final time complexity is O(N^2 x 2^N).
As you mentioned in your video: Time complexity = Number of states * Transition Time.
I can agree with you that we have 2 ^ N states. But I don't understand why the transition time is N ^ 2. In this video you said N ^ 2 because we're matching every person with every job but ( i think you referred here to the c[ j][i] but for a state i we only try to match the n works that we have to solve the task i. For me it looks more like the transition time is N and the final time complexity is O(N x 2 ^ N). I may be wrong here so please correct me.
Time complexity is O(N^2*2^N).
I might have messed up while saying that the transition time is O(N^2), it is not it is O(N), sorry about that.
Here is the analysis:
1. Number of states = N*2^N.
2. Per state I look at N other states(refer to the for loop inside solve())
3. This gives me a transition time of O(N).
4. Overall = N*N*2^N
Let me know if this helps :)
@@AlgosWithKartik , thanks, it's clear now :)
Nice explanation 👍
Nice Explanation bro 👍👍
THANK YOU A LOT
Thanks sir, Really good explanation.
great video
2^n is for permutation of jobs that will be assigned to people or permutation of people who will be assigned jobs?
thanks for teaching this topic :-)
You can also use the code editor of dark theme/background. Everything else is 'Perfect'.
Kartik, Time Complexity of your code here is O(N^2) right ? Because we are not iterating through every possible-mask here. We are just seeing for jobs [0, n) if they are set in mask or not which O(N) * recursion Time O(N) again. Please do correct me if I am wrong.
great explanation
good explaination.
Wow it is good.
can we relate this problem with N-Queens problem?
Bro, very nice explanation. Can you tell me if we want to find that subset which has minimum value, how can we do that ?
Bhaiya Codeforces ki problems krwa do dp with bitmasking prr bhot help ho jayegi
Bilkul bro codeforces ki R1800 se R2200 ki range me problems cover krrunga bitmasking ki.
For now yeh choose krri as an introductory problem.
Is there a OJ so I can submit this problem ?
Why memset(dp,-1,sizeof dp);
and why not this one memset(dp,0,sizeof dp);?
and why you used it in locally ?
i used int dp[21][1
Instead of mask, why don’t we just use a regular integer here? Masking made it a bit complicated isn’t it
Really helpful
Thanks for the great solution. But imo it wasn't at all hard, bcz i have seen lot more hard questions asked by Google.
Actually the motive wasn't to solve a hard Problem but to have an introductory problem for dp bitmask.
Hopefully down the line the difficulties will increase :)
suggest platforms also where we can submit the problems
Thanks, but can anyone provide this problem on an online judge?
Thanks sir
thanks sir
One of your states is redundant , it can be calculated by no. Of set bits in mask
how to write the iterative version of it ??
nice explanation ..:)
time complexity should be eloborated more. if you are making the videos for redcoders then you should mention in the playlists.
Hi bro,from where i can practice dp problems? I just completed dp section on cses.
Try Atcoder educational dp contest, spoj, codeforces
i guess in for loop it should be C[i][j] nor C[j][i], plz thell me if i am wrong and why
Sir please add more videos on bitmasking.
Yes, I will.
In cf u preferred top dowm or botm up?
Whichever I can code in less time.
@@AlgosWithKartik like top down is always easier to think but on the other hand most of the CM's,Mastrs do bottom up. Is using memorization a bad practice? Do companies ask both approaches?
@@AlgosWithKartik Even i have the same doubt..i am able to dp problems in top down manner ..but face difficulty in bottom up.
What is the problem no for this question on leetcode or any similar question?
Nice!
Iam learning this in my 1st semester of college.(iam comfortable with what I have learnt). Am I going in right path sir....?kindly reply sir...
Yes you are!
I hope you have a bright future ahead keep going :)
Sir please enable caption
yes please add it
Please Please answer this. If we set the ith bit in mask saying the job is taken but also after recursion undo (backtrack) and store to dp matrix (memorization) would it be ok ?
// mask initially worker = n-1 , (i
Looks alright to me(skimmed through)
Isn't this similar to knapsack 🤔
sir,how did you add paint for sublime text
Epic pen
It's been 2 days...no videos?..we are waiting
Was out with friends, now I'm back on work!
Expect videos soon and do share the channel with other people who might find it helpful!
@@AlgosWithKartik definitely
Kaha ki problem hai ye?
Common problem h bro kaafi, assignment problem kehte hain isko.
University me padhatey hain Hungarian Algorithm.
I thought dp with bitmask samjhane ke liye achhi rahegi.
@@AlgosWithKartik Great bhai..Thxx
trats: 5:35
time complexity can be hard to someone and you have said it in 5 seconds. why dont try to eloborate more ?
Is this soln correct
int solve(vector &cost, vector &vis, int col)
{
if (col == cost.size())
return 0;
else {
int ans = INT_MAX;
for (int i = 0; i < cost.size(); i++) {
if (!vis[i]) {
vis[i] = 1;
ans = min(ans, cost[i][col] + solve(cost, vis, col + 1));
vis[i] = 0;
}
}
return ans;
}
}
int main()
{
int N;
cin >> N;
vector cost(N, vector(N, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> cost[i][j];
}
}
vector vis(N, 0);
cout