Complete Dynamic Programming Practice - Noob to Expert

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

День тому

Problemset link: codeforces.com/contestInvitat...
Harmonic series blog: discuss.codechef.com/t/more-i...
I end up covering problems A-H and K in the problemset.
Here's part 2, where I finish it: • Complete Dynamic Progr...
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

КОМЕНТАРІ: 167

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

@dipankarkumarsingh Рік тому

😊 Good to See you back on UKposts [ after a long break ] .... And yes this video is really Quality content [ with Lots of Varity on Questions ] thanks for the video

@austinwitherspoon4940 Рік тому

.lm . . .. . . .... . .. . .. . . ... . . .. . . . . . . . . . ..... .... .. ........ . . .. . . . . .. . . . .. . . . ... . . .. .....

@austinwitherspoon4940 Рік тому

O ... ..... . . . . . ... ..... .... .. ... . . . . . . ... .... ..... .. .. .. . . . . .. .. .. .. mm.. ... ...... ...... . . .. .. .. . ... . . M................ . . ..... .. .. ..... . ......... .... .... . . .. ....... . ... . ....... ... . . ... ................. ..

@Gukslaven Рік тому

Honestly the best tutorial I've seen for DP. I'm working through the problems and referring back to this vid as I get stuck, making progress :)

@minfoodtravels Рік тому

programming becoming more widely available and newbies like myself find your methods of teaching very easily absorbing into my brain cells, I thank you for your great and entertaining content and deep knowledge on DP.

@sayantansinharay9161 3 роки тому

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

@Code_Note 2 роки тому

lol didnt expect u here

@sayantansinharay9161 2 роки тому

@@Code_Note brooooo my school kanishk i too do cp a bit bro connect up you on linkedin or discord

@Code_Note 2 роки тому

@@sayantansinharay9161 ok

@Cpp_For_Life 4 місяці тому

I am 19 too 😢

@victorleroux-avantin-sq1rv 10 днів тому

🎉❤@@Code_Note😂❤😂

@abhinavghosh725 3 роки тому

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 !

@shreyghugtiyal4118 2 роки тому

exactly😂

@Shreyas535 Рік тому

For me the hardest part is to identify a greedy problem. I have the least success rate in identifying greedy problems.

@therealg9542 3 місяці тому

If the problem can be solved by solving subproblems, the problem is most likely a dp question. If the solution to the current subproblem cannot be solved using previous subproblems, then the question is most likely not a dp question. dp intuition requires practice.

@timothygao9442 3 роки тому

"Improving is a random thing"

@ColinGalen 3 роки тому

There are probably a lot of good quotes in this video lol

@harshadaggarwal6029 3 роки тому

@@ColinGalen my favorite at 2:10:20

@alonsocerpa2745 2 роки тому

@@harshadaggarwal6029 hahaha

@watchlistsclips3196 3 роки тому

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.

@stemwithsagnik7096 Рік тому

Thank you so much for this series!

@jakeambrose4294 Рік тому

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!

@koocheukkeijacky9704 3 роки тому

Thank you so much! I learnt a lot in all of your tutorial stream

@DonTequilon Рік тому

what an incredible video, hope you the best.

@kinershah464 Рік тому

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.

@professionalFriend 3 роки тому

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

@dangduong5362 2 роки тому

thanks for your helpful lecture

@sazidimtiaz831 3 роки тому

thank you very much!❣️

@sunshodan5883 3 роки тому

please keep making topic streams

@harshsrivastava5124 3 роки тому

Thanks a lot it really helped.. Hoping to see more of these streams :)

@dejavukun 3 роки тому

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

@lakshyabamne4303 7 місяців тому

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

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

@abhaypatil2000 3 роки тому

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

@pranjalpriyadarshi1289 3 роки тому

How do I get the list of all the codeforces mashups which you have created!

@lingcheng2971 2 роки тому

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.

@vishnusingh4118 3 роки тому

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!

@ColinGalen 3 роки тому

Yep, this is an older video, and I have a much better mic for some of the newer ones.

@nathann6518 3 роки тому

@@ColinGalen I need help, for mashup A, I do get 2*f(n-2), do to probability, but I don’t get f(n-2) + f(n-2) and how you got that solution using DP

@user-cr6gp5qf2m 3 місяці тому

Hey @ColinGalen I did not understood why are you using min() in mashup C's ?

@karasensei2308 Рік тому

not know , but just know you've affected my life, and apparently tens of thousands of others, in an imnsely positive way. Thank you

@eshumanohare7614 Рік тому

A non-dp solution to problem G #include #include 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

@igorbeliyaveski7600 10 місяців тому

Thank you!!!

@trillionman2105 Рік тому

Probably the first two problems would be better in a tutorial on when you should avoid dp solutions even if they are possible.

@sachit16-26 3 роки тому

will you conduct more such? highly needed bruh!

@ColinGalen 3 роки тому

Yeah, I do plan more in the future, there's just not much time for me to do them currently.

@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

@akashbhoi1951 Рік тому

Is this the extension or something else (the box with the right arrow) :)

@Spectrum_Aerospacejet_Lab 7 місяців тому

Robots and Relays.

@abhinavrajhans1107 3 роки тому

i do not understand the dth question in that we can keep him awake for k straight minutes and if we choose start of 3 then we can keep him awake till [3,3+3-1] which includes 5 2 5 so the sum is 12 but how sum is coming as 14 please help ?

@Poignant_ 10 місяців тому

Hello, in the past couple of days my internet started acting very strange, my lights are a solid green and a blinking orange but whenever i try to play an online game i keep getting disconnected but the little icon in the right corner still says in connected, how can i fix this?

@sarathkumarnallendhiran2815 Рік тому

Please do a topic stream on recursion and backtracking.

@nallasivakrishnasai1122 3 роки тому

@Colin Galen In problem E(office keys) Can you please help me in formally proving that the greedy way of having continuous assignment between the keys and people is optimum. Anyone's help would be really useful.

@dakshchhabra5975 2 роки тому

Lets say P1 and P2 are positions of two people and k1 and k2 are positions of two Keys I am going to explain one of the case when k1>P1 and k2 > P2, other 3 cases you can deduce by yourself Distance if we assign P1 to k2 and P2 to k1 is K2-P1 + (p2-k1) if we assume P2> k1 Surely this dis is greater than K1-p1 + (p2-k2) because P2>k1 Other cases you can prove similarly

@prasaddash5139 3 роки тому

i am still not able to get the C problem can any one suggest a place to read it again

@anhuynh1172 3 місяці тому

You help me a lot

@haricharanpal1761 3 роки тому

Can u make a video on how do use templates

@Phoenix-xi2gy 3 роки тому

Can you please provide some resource or some intuition for "taking continuous keys will give us optimal solution" part of E problem Office Keys

@shreyashachoudhary480 2 роки тому

Thanks!

@dontony7071 3 роки тому

Next one on graphs and trees🤔

@dheerajbhagchandani7529 3 роки тому

yeah it's good for me

@abhaypatil2000 3 роки тому

I am not comfortable using push dp. Is it ok to use recursive dp. I mean are there any questions which can be done by push dp and not with recursive dp?

@ColinGalen 3 роки тому

Yes, there are some. However, they usually involve difficult recurrences, and won't show up until the higher end of the difficulty scale. In almost all cases, it's completely fine to use recursive DP, and whatever you use is preference. By the time you get to the point of having to solve the harder ones, you'll probably be comfortable enough with DP to be able to do it.

@prateekchauhan9044 3 роки тому

Please explain codechef november long questions

@laraibanwar1618 3 роки тому

Hey colin can u plz teach line sweep algorithms with example plz.. Ur videos are awesome tho. Great work and i like the ways u teach. Best 👍

@user-io4sr7vg1v 4 місяці тому

FFT is not DP. It uses the decimation algorithm because so many of the elements end up being zeros. It can be 'memoized' but to break it up into smaller subproblems doesn't give any benefit.

@ramhemanth1132 Рік тому

Can you share the code for each problem please.

@brandonstark4133 3 роки тому

Why can't I join the MashUp GYMS(PROBLEMSETS)?

@shivarajpatil8699 Рік тому

Do you actually Questions like this or do it in the mind?

@Axjira 2 місяці тому

I woke up to this. How does someone end here starting from brawl stars kmak

@parthpawar7837 3 роки тому

In problem A, f(n) = 2f(n-2) because we choose a 2x3 block (which has 2 orientations) and multiply with the solution of f(n-2), hence 2f(n-2). But we can also chose that 2x3 block in n ways, so why isn't the relation f(n) = n*2*f(n-2) ?

@ColinGalen 3 роки тому

Because the location of the block is irrelevant - if you put it somewhere in the middle, it'll be equivalent to putting it in the middle later (i.e. the order in which you place down blocks is irrelevant). So that recurrence will drastically overcount. I use the recurrence I do to make the subproblems independent - if I place it at the (right) end of the current grid, then it will be completely independent from the rest of the grid, and thus not overcount.

@parthpawar7837 3 роки тому

@@ColinGalen Makes sense. Thanks for clearing this

@nimanthadilz 2 роки тому

Hi Colin, In problem E-Office Keys, I understand why you say two people can't cross their paths to get the keys. But you didn't say why you choose key positions continuously. I mean if first person is assigned to ith key position, second person is assigned to (i+1)th position and so on. What is the reason for this ?

@theblinkingbrownie4654 Рік тому

The second person is not assigned to the (i+1)th position, he has the CHOICE to choose the (i+1)th position and any key after that

@AKRahim-wg5dm 3 роки тому

golden voice

@samarjyotiray3488 3 роки тому

5:41 "No Way!" t'was funny 😂😂 You must be working with Python, I guess?

@vinicus508 6 місяців тому

I slept with UKposts on and this video started playing. I dreamt about a guy who was solving the Navier Stokes millennium equation using some sort of toy that he moves around with his fingers (that was you typing). Lmao

@M4rt1nX 10 місяців тому

Yeah, the algo got me here. It was on autoplay while I was sleeping.

@nguyenhoangdung3823 3 роки тому

what? Discord LIGHT THEME ???

@Artaxerxes. 3 роки тому

ikr its blinding

@bobapplebob9695 10 місяців тому

I incredibly doubt you will see this due to the fact that you apparently have a ton of subscribers all of a sudden, but thought you'd get a kick out of me having found this video through autoplay while asleep, you can imagine my surprise when I woke up and I heard a voice I recognized.

@adcaptandumvulgus4252 Місяць тому

As soon as I heard the word math I went "nope"

@docstyagi7775 3 роки тому

In problem E, office keys. Taking a contiguous segment of keys is always optimal. Can this lead to a better complexity than O(people * keys).

@newman6492 Рік тому

I think you don't know what is row and what is column?

@anunaysharma5609 3 роки тому

Hey Colin, can you please make a video for beginners on how to become red on codeforces, thank you

@pulkitjoshi28 2 роки тому

Hey, in problem A, shouldn't f[0] be 0, since a 3x0 grid doesn't make sense.

@AlgorithmAlchemy69 8 місяців тому

F can be easily be solved using dearrangements!

@eliotcamel7799 10 місяців тому

First few problems be like: "Imagine doing the O(1) solution when there's an O(n) solution"

@MSISAmar 3 роки тому

Pls make more videos🙏

@yashkumarsingh9713 4 місяці тому

do one for recursion

@SonicCGames 10 місяців тому

oh loawd im coming

@udoigogoi6828 3 роки тому

Galen colin in cp:🔥🔥🔥🔥🔥🔥

@vinhnghiang1273 Рік тому

what is this IDE?

@alphaco3868 2 роки тому

It took 1 month to complete dp where some people trying to learn dp in one day ..... :D

@josephwong2832 2 роки тому

awesome stream colin

@shubhamk840 3 роки тому

Since you have crossed more than 5k subs, you should now switch to something like electronic writing pad I guess.

@ColinGalen 3 роки тому

soon™

@cpwithsundar 3 роки тому

what is he using in this video to write

@derilraju2106 Рік тому

@@cpwithsundar ms paint

@vedbhatawadekar6842 3 роки тому

can someone explain what is the time complexity of solution in K?

@huhuboss8274 Рік тому

Only 30k left until he can pin comments

@jakeambrose4294 Рік тому

theres very very very little amount of resources on the internet that help people from 0-100 with constructive resources and telling them what to drill and practice.

@itz_me_imraan02 2 роки тому

Couldn't understand some problems clearly....you could have explained some problems in more details....don't recommend this for beginners 😔..

@rightspotadvertising1786 Рік тому

Woow woow

@revanthkalavala1829 Рік тому

Problem F should be more suitable in Math category rather than DP.

@pleasesirmorevideos4684 3 роки тому

Nice Stream just avoid reading chats so much, they distract a lot rest all are fine

@imranif3899 3 роки тому

Why? It's his channel, he has the complete freedom to do streams the way he deems it fun as well as informative. It's no easy task doing a 4hr streaming without taking much of a break.

@pleasesirmorevideos4684 3 роки тому

@@imranif3899 you are so cute

@imranif3899 3 роки тому

@@pleasesirmorevideos4684 lol...couldn't you just avoid reading my comment? So distracting, wasn't it? I highly doubt your ability to do what you just said.

@pleasesirmorevideos4684 3 роки тому

@@imranif3899 you are still so cute

@ColinGalen 3 роки тому

@@pleasesirmorevideos4684 Bruh, even if you know each other, don't be toxic

@pinyichang4680 Рік тому

dynamic

@Eurotool 5 місяців тому

Dreamed of this annoying know-it-all from my previous job He was "teaching" me things I already knew He said "now I'm gonna teach you recursion" And I replied I ALREADY KNOW WHAT THAT IS And he flat out ignored me Then he said "okay to learn recursion we're gonna use fibonacci's sequence. but first let's learn what fibonacci's sequence is" I was like NO I KNOW WHAT IT IS but again he ignored me Eventually I was fed up so I left the room But he CALLED ME and kept explaining fibonacci's sequence Then I woke up and found out UKposts was playing this random programming tutorial

@user-xb8jc9bq3b 16 днів тому

@ColingGalen, do you drink coffee?

@mamtachahal1277 3 роки тому

BTW how old are you?

@ColinGalen 3 роки тому

@iitnakanpur.. 3 роки тому

@@ColinGalen 😲😲😲😲

@sachit16-26 3 роки тому

@@ColinGalen seriously??

@miriotogata8993 7 місяців тому

28:00

@hacksource1784 Рік тому

GLAD I MET HACKERS SUMMIT WHO SORTED MY GRADES ISSUES,THEY CAN HELP YOU

@xagiziga 10 місяців тому

wew

@AHMEDSAAD-od3bg 2 роки тому

Did'nt you go to ioi??

@user-cr6gp5qf2m 3 місяці тому

1:57:11

@Keitan97 10 місяців тому

I set UKposts on auto play when I was asleep… where the fuck am I?

@extraFart Рік тому

2:02:34 onichan

@vimmiduggal6658 Рік тому

1:23:58 For personal use, please ignore

@t.r.venkat7661 2 роки тому

ur too much into live chat!!...this turns irritating at a point

@DoPlayGameYes 5 місяців тому

yeah i can really tell you are 17 right now. i couldn't sit for 10 seconds of this

@Oliver_twist00 10 місяців тому

Remake it big bro

@a.htonmoy1896 2 роки тому

Why this people in the chat talk more about other shits than the problems in a topic stream ! It's irritating 😑

@saranuwatpanon2505 10 місяців тому

offer

@WalkingHeadPro 10 місяців тому

booooorrrrinnnnggg

@vaibhavtiwari1114 2 роки тому

#recursive code for C. Recursion with caching or simply memoization. dp = {} n = int(input()) inf = 10**17 s = [] def string_to_mask(string): return 4*int('A' in string)+2*int('B' in string)+int('C' in string) for i in range(n): cost,vitamins = input().split() curr_mask = string_to_mask(vitamins) s.append([int(cost),curr_mask]) def solve(i,mask): if (i,mask) in dp: return dp[(i,mask)] if i==0 and mask==0: return 0 if i==0: return 10**15 mn = 10**15 for msk in range(0,8): if s[i-1][1]|msk == mask: mn=min(mn,solve(i-1,msk)+s[i-1][0]) mn = min(mn,solve(i-1,mask)) dp[(i,mask)] = mn return mn ans = solve(n,7) if ans==10**15: print(-1) else: print(ans)