Complete Dynamic Programming Practice - Noob to Expert | Topic Stream 1

I end up covering problems A-H and K in the problemset.

Note that problem explanations are probably long because of interacting with chat, not necessarily because of difficulty. Also, sometimes I refer to the problemset as a "mashup" because Codeforces calls it that.

Timestamps:
Intro 00:00
Intro to DP (Fibonacci) 04:19
Mashup A 21:20
Mashup B 45:37
Trying to pin a message 52:05
Continuing B 56:25
Mashup C 1:08:49
Mashup D 1:30:45
Mashup E 1:46:22
Intermission (+ water bottle inspiration) 2:12:05
Mashup F 2:17:45
Figuring out what a derangement is 2:48:59
Mashup G 3:00:24
Mashup H 3:28:14
Mashup K 3:39:26

[ColinGalen]

Seems like this video is hitting the algorithm. For those of you who are new here - I have a face now, and also a significantly better mic :)

[abhinavghosh]

for me the hardest part of DP is finding out that this is a Dp problem .
btw you repeatedly said rows in place of column and vice versa many times, other than that it was perfect !

[sayantansinharay]

I am 19 :) still watching you learn something. One suggestion my friend please don't get distracted by live comments

[kinershah]

Great video. I tried my best to follow and understand the concepts.
Just one suggestion, if you can use better variable names to represent DP states. Using variable names like i, j and k can be confusing sometimes.
I know you are used to using shorter names since it's way convenient and fast for CP but I will really appreciate if you could use slightly longer and meaningful names, of course only during explanation for better understanding and avoiding any confusion.
Again thanks for great explanation. Really appreciate the time you have taken to explain the DP concepts.

[vanchark]

I appreciate you putting out this free educational content, but a suggestion would be to try to stay focused while explaining your thought process. It's hard to follow along when mid-thought you reply to chat :(

[watchlistsclips]

I am soo glad that you are making a video on graphs .It will be lot more helpful to many people if you make videos on problems involving greedy method like u made for topics such as trees, dynamic programming . Like where we need to use this approach. We have very less videos regarding this.

[vishnusingh]

Thanks for these vids man! One suggestion - The audio quality is a dampener to the amazing efforts you're putting in. If it's a short video, it's bearable, but in long streams like these, audio is actually way more important than video. If you could invest a bit in a better mic, it would do a world of good to up the quality of audio. Thanks again for your efforts and value addition to the community. Learning a ton from you!

[timothygao]

"Improving is a random thing"

[PrinceKumar-glfk]

solution for 1st question
#include<bits/stdc++.h>
using namespace std;
int pow_2(int n){
return (1<<n);
}


int main(){

cin.tie(0);
int n ;
cin>>n ;
long long x=pow_2(n/2);
if(n%2) cout<<0<<endl;

else cout<<x<<endl;
return 0;
}

[lingcheng]

For problem F, your original code is almost passing.
if (k>=4) ans += 3 * nck(n, 4) + nck(n, 2)*nck(n-2, 2);
can pass all tests.

[dejavukun]

Thanks a lot for the contest. Please avoid getting distracted by the comments. Breaks the flow of explanation.

[eshumanohare]

A non-dp solution to problem G

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){
ll v1, v2;
cin >> v1 >> v2;
ll t, d;
cin >> t >> d;

ll ans = v1 + v2;
for(ll i=1; i<=t-2; i++){
ans += min(v1+i*d, v2+(t-i-1)*d);
}
cout << ans << '\n';
return 0;
}


Basically, in order to maximize the sum of all numbers, we can assume the next element to be d greater than the previous element. Apply the same logic backwards and choose the minimum of two choices.

[professionalFriend]

Good Work...First i can try questions on my own and see your video if i get stuck at some problem.

[zoeylovegood]

I have no idea what complete dynamic programming is, nor do I ever imagine I'll ever learn, but I did somehow wake up at 3am from a very bizzare dream about it due to youtube's autoplay. So thanks youtube for the 3am lesson that I didn't ask for.

[jakeambrose]

Wow this seems like what ive been dying to find. I sure hope it is. I appreciate all your effort and sharing the knowledge my friend!

[johnnycharles]

I fell asleep listening to a podcast and then this came on afterwards. I had anxiety dreams I was in college again, and you were trying to teach me differential equations, but nothing you said made any sense because this isn't a class on DE.

[mangalegends]

So I just realized something after see you do Mashup B. One of the big parts of my struggle with DP questions is understanding what the heck the question is really asking. I saw the solution to the number of typeable substrings for the example string "abacaba" is 12, and I could not see how there are 12 substrings. I could only count 5:

a
ab
aba
ba
b

I couldn't fathom how there's 12 until like the next day I took a look again and it occurred to me that they're counting the same character multiple times if it's in the string in different places. So they're not looking for the count of unique substrings, which was pretty counterintuitive for me

[inspired_enough_to_grow_up]

will you conduct more such?
highly needed bruh!

[lakshyabamne]

my right ear enjoyed this stream very much, cant say the same for my left year though :)

[abhaypatil]

Definitely you are getting to 10k.cause once a person start watching you he is going to stick with you