Codeforces Div2E: DP with Bitmasking
Vložit
- čas přidán 13. 09. 2024
- Hi Everyone!
I hope you all are doing well and enjoying the bitmasking series.
Let's take the difficulty level up a notch.
I'll discuss a problem named Fish that comes from a Codeforces Divison 2 round and is the problem E of that round.
Problem link: codeforces.com...
Enjoy watching!
If this helped you make sure to hit the like button and subscribe if you still haven't subscribed for more quality content!
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
Most utubers keep doing the known famous dp related problems , u are doing something which is difficult and unique problems and also on top it's DP !!!!!!! , love it , keep doing it , most of us are eagerly waiting for such good DP problems explanation :)
thankyou!
Exactly , Kartik sir is dope in all kinds of dp whether it is digit dp , bitmasking , dp on trees .
Kartik bhaiya pls make more videos of dp ( from all topics ) ..
Loved ur videos btw 🤩🤩
Wow am just back at this message after a year and I can see almost 50 likes, amazing, seems like it's really time Kartik bhaiya pls come back
Space Complexity: O(2^N)
Time Complexity: O(N^2 * 2^N)
Why not the Time Complexity is O(N^3 * 2^N), as far as I am calculating, the solve function(bitmask DP function) is of O(N^2 * 2^N) and we have to calculate for all 'i', so the overall Time Complexity for that, might be O(N^3 * 2^N) ?? Can you explain how it's O(N^2 * 2^N) ?
You make DP problems seem so easy, the way you explain is so clear, thanks
Thanks Vivek :)
this guy never fails to surprise the audience
Didn't understand completely in 1st time. But watched again and tried writing dp states and transitions along with video and understood completely. Thank you for your efforts in teaching🙏
After each and every video, i am becoming a bigger fan of you! Explanation at its Best!!!!
you know what? I love your channel so much! It helps me so much to understand these kinds of topics. Please, keep going. There are a lot of people who waits you, including me
You explain these hard problems so perfectly that they seem so easy, thanks a ton, big brother 💙❤️
This is called real CP content 🤩. Thank you.
your explanations have given me deep insights in the dp, I have recommended you to my friends and teachers as well, hope you will make more videos like this
I solved the question in my mind before you started explaining it. You're explanations are that awesome....😀
thanks man
Sir please never stop making videos on such topics and also I have a request for you to cover matrix exponentiation as well.
Thanks for the video. concept is much clearer now.
Great.
will be waiting for next video.
Will add soon.
You way of explaining things is awesome🔥🔥keep making these awesome videos
Thankyou Rishabh :D
gold content!
Sir ek video roadmap pe bana dijiye...kaise koi sirf div2a problem solve krne se lekar div2 ki saari problems solve krne tk jaa skta hai..
Bro watch this ......................nice roadmap + preparation strategy...........
czcams.com/video/zZOQVLll9u4/video.html
Try krrta hu bro jaldi hi banane ki
awesome video dude,loved it!
Thanks man.
hello sir,at first i want to say thanks for creating this playlist,its helping a lot to learn bitmasking.I have a question I didn't understood the part why you summed all the probability at 6:33 sec.Always I didn't understood why you multiplied prev_day with p_move.
❤️❤️
Please 2 more problems to the set or give 4-5 problems which use dp with bitmask in easy , medium and hard difficulty
great video.....
did not undertaand kc2 . please could u explain sir
Awesome solution. Can you please share some good tutorials on probability. I am familiar with basics but want to learn probability in advance for competitive programming pov.
try CLRS or Codeforces blogs
The things is how would I know that we should go with 1-d DP or 2-D dp. Here you're using 1-d dp. But max dp with masking have 2-d dp.
You are my savior :)
In pmove () function why u consider jth set bit because it has to loose
3:10 - 13:18
Sir, will you be uploading more questions on dp with bitmasking??
Yess I will.
Already planned 2(solved 1), Currently a bit involved in other work.
Will try to add soon :)
could you suggest some more problems to solve to cover more varieties
can anyone please provide me the full solution, I am getting wrong answer. I also checked code from the video still getting wrong. Printing 0 every time. Please help.
Check for my submission on codeforces for this problem.
Kartik Sir.....here is a request ....sir please make a series of videos on DSU(disjoint set Union) as i felt your dp series very interesting if you make videos on these concept it will be great ................... or please share some good resources to learn DSU........................ i am fully enthusiastic in learning this concept i have also seen some videos but all them were quite basic level or boring.......hoping for a reply
BTW nice explanation it was a nice problem
DSU is easy you can learn it from hackerearth and by solving their easy questions
@@pleasesirmorevideos4684 sir i need some advanced level content........... you can search on youtube there is nothing that special ............. i am currently studying Dsu and trying problem on hacker earth ....yes easy ques are doable but many times i stuck on problems of diff >1700 on codeforces ...their tag may contain DSU but editorial does not have a dsu solution..sometimes comment section helps me but it is not for always .....also i am finding Dsu quite interesting topic ..................it will be good if you just share some resources to learn DSu quite well
I will try to make for that but it will take some time
@@AlgosWithKartik no problem ....until that please share links of some good resources for dsu....
@@classcure9769 try codeforces blogs
DED
@AlgosWithKartik please help its giving tle on 4th case idk why
//#define prD(x) cout
Sir, please ye videos Hindi me bhi bna do..
Sir, are you going to upload the solutions of codeforces round 660 div2 solutions?
Not this time
Still not able to understand 😢. What should i do
Did you try the other problems in the Bitmasking playlist?
Yup i solved assign problem on spoj myself after i watched your video. I think i lack probability part here.
Previous day, premask and all egde corner i still cant visualise it
Hmm try out a few lectures on probability and expected value which might be beneficial :)
I repeat, Kartik Arora is GOD.
Arre bhai bhai bhai xD