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

hey guys i hope you can hear me i also hope this lawn mowing that's outside right now is like not hurting too bad because i know that it's very loud to me could you guys tell me how the audio is and if this is like very annoying in the background i hope it's fine everything should be good okay so let's get started hey crystal violet what's up this is a tradition fine with that um okay let me just wait you can't hear anything um that's not good maybe it's your volume because it seems like obs is at least picking up my stuff oh hang on let me show this to my discord because it's always um okay okay cool all right thank you here let me just send this off first usually do this and you know if you want to see this discord you can always go right into the description but um that should work all right cool so now the plan is just to do what i was saying i'm going to do these i have this mashup of problems that i created the first four are sort of kind of hand-picked and the last 11 are harder and also of random difficulty so should be interesting to see how it works but um wait one second let me also um get my chat open somewhere else so i can be able to read it and do stuff at the same time because you know it's kind of smart to set this stuff up beforehand but it's not a big deal alright so first i'm just going to um first i'm going to make a thumbnail because i'm very prepared for this setting up the stream as the stream is going on not suspicious at all uh it's right here i'll just add this you know how it goes because this old thumbnail is the same one is um yes it should have a few bit mess things and um yeah okay ideally don't do spoilers that's not um ideal one second setting up the stream as it's going on okay perfect so let's begin with just a brief idea of what dynamic programming actually is for the people who are kind of like unfamiliar with it and at the same time this can serve as review so i'm going to go over a problem that like basically everyone uses but the reason everyone uses because it's a really simple and nice introductory problem so um do you need to know basic dp i mean it helps to know what the concept is but you don't necessarily need to um like be able to apply it yet i guess yeah no spoilers okay so i'm gonna go with uh fibonacci because everyone knows that so the basic idea is you have the sequence let's call it f of n and it has a formula for it which is essentially um it's a piecewise function which means that like for certain values it behaves one way and for other values it behaves otherwise so please teach you used to go mowing maybe later i'll take custom requests after we get through this so f n is defined as i think it's zero if n equals zero and then one if n equals one or um the other definition is f of n minus 1 plus f of n minus 2 the previous two elements oh mowing mist no no no no not that one not that one i can't do that one okay now this is the problem so if we were to write some program like just straight up uses this definition like for example here's what the code would look like um it would just be this and we just straight up write code that uses the definition of fibonacci now think about like what happens with this code so we begin by let's say we call f of 5. this is also kind of a well-known diagram let's say we call f i'm just right now i'm just going briefly over what dynamic programming is like why are we doing this what is this useful for why is it so necessary and then after that i'll get into the problems so f of 5 well it relies on f minus 1 which means that it relies on f 4. so this is going to call f of 4 actually i'm going to do f of 3 first but because it also relies on f minus 2. so it will call f of 3 and it will also call f 4. okay in a similar manner we can kind of um we can just like keep on oh i didn't make these problems i just kind of gathered them around we can keep expanding this tree now f of 1 is just f 1 is just like we know it it's a it's like known so this isn't going to generate any more recursive calls but this will keep going down to f 0 and f of one now we do the same thing here we we go to f four this is going to call f of two and f of three and then we can expand all of these out tediously and annoyingly and pointlessly because that's what happens like look at how big this tree is for f of five like we require we want to know six values but look at how much work we're doing to do this right like this this some of this is just pointless and actually look at this this this whole subtree of calling f of three and this this is the exact same thing so like why are we doing it again we just we just did this here why are we doing it again here and if we expand out to higher higher values it's going to like repeat more and more and more why are we doing it again so the whole point of dynamic programming is that we don't do it again we we figure out the value of f of 3 here and we know its answer and then when we get to this point where we require that we need to know the value of f of 3 again well we already know it so we check that we already know it and then we cut off this whole thing here we don't redo this because we've already done it that's what dynamic programming is essentially we store answers we've already computed and used those stored answers to prevent ourselves from wasting time by redoing a bunch of things so in terms of implementation how would this work well say you just had like a big array um let's call it a cache for example yeah memorization is one form of dp i'm also going to go over the other form like this is called recursive dp because it's um a thing let's say we just had a cache which was of size like it would store all the numbers from zero to n so we call f of um five and then we do the same thing it relies on f of three and f 4. so now we do the same thing we rely on f of 1. f of 1 we find the answer for so now we store that in the cache and f of 2 we don't know the answer for so we keep going this goes to f of 0 and right f of 0 and f of 1 both of which we already know the answer for and then once we do this once we do this now we get the answer for f of 2. all right this is going to be introductory dp i'm not really going over advanced concepts here probably not in this stream at all because most of these problems aren't designed to be the the crazy the crazy stuff i'm not making cash i don't even have monetization on i'm just uh doing this right okay so now f of two we just learned we used f of zero and f of one and now we know the answer for f of two so let's put it in the cache so now we've cached um we've cached f of zero we've cached f of one we've cached f of two whatever these ants oh yeah yeah cache okay okay sure sure scic but we've cached these three values and now we know the answer for f of three because it relies on these two and we know both of them so now we've cached f of three and comma before space okay whatever and then so now we have to compute f of 4. yeah f of 1 um i'm not sure so now we call f 2. now normally f of 2 would also call f of 0 and f of 1. but first before we do this we check that f of 2 is in the cache and indeed it is so instead of recomputing f of 2 we simply use that answer that we already know and we cut it off so f of 2 is done in one operation instead of n3 and then we do the same thing for f of 3. f 3 is already in the cache so we use that answer and we cut it off and that's it so what it means is every value is computed exactly once so there's no sort of like big blowing up of this tree everything is done once that's the idea and this is called memoization oh and by the way once we do this we know the answer for f of four so we can also cache four and then we know the answer for f of five so we're done this idea is called memoization where we memoize like memorize but like without the r for some reason they decided this name was we memoized the answers that we've come up with before and now we know now we know them so we don't waste time redoing it so instead of this exponential complexity that we would have originally had like of 2 to the n we compute everything once and like everything only relies on two values so it just becomes o of n in terms of complexity so um in terms of code this is actually very simple cache let's do like let's say we're computing f of 20. right and then we use a negative one because no fibonacci numbers can be negative one we use negative one to represent a number that doesn't exist yet you can also do um something like this where you just keep a boolean array of whether you found the answer or not and then you can use that as reference but let's see so we optimize it like this if we already know this answer is not equal to negative one instead of doing the recursive formulation just do this return cash event i'll do the subscriber count when we start um the um like the actual problems okay so now we know that the answer is going to be f of n minus 1 plus f of n minus 2. so why don't we cache that now and then return that now this is going to be much faster because again it uses this idea of storing answers we already know so this is memoization and the other way to do it is the more popular or the more like it's more of what you would call dynamic programming yeah everything's going to be available for rewatching so i'll have the archive up on my youtube so the other form is dynamic programming where instead of like doing it recursively where we do a cache and store the previous answers instead we kind of like we we sort of more mess with the idea of using previous answers let's compute let's compute first f of zero then we do f of one then we do f of two and then we keep going in increasing order until we get to f of n right okay why is this useful because like any value of f of n is only going to depend on previous values for f of 3 we only need to know f of 2 and f of 1. so if we make it so we compute all of the previous values before we compute this one then we're automatically going to know the answer to um to f of 3. and then when we get to computing f 4 we already know the answers for f 3 and f of 2. and then we just keep going right so unlike memorization which is recursive dp this is sort of like iterative dp where you would do it as a loop and so you would literally just um like you literally you would literally just do it and then you store all these answers in sort of the same kind of cache but it's an array instead yeah it's um bottom up meanwhile memoization is sort of top down you start at the top and then you like propagate down and compute the states like that right so you just do it in this order and then you say in array format f of n is equal to f of n minus 1 plus f of n minus 2. it's just an array right so here's the other way you would do this i'll delete memoization and usually with arrays like this you would just call them dp actually i'll call them f i suppose n equals 20 then actually we wouldn't do the base cases in the loop so first we begin with the base cases we know f of zero oh and base cases are just values you immediately know like for example the base cases in these would be zero and one because they don't rely on previous values how much will the stream cover yeah it'll be like a lot of problems i suppose probably gonna go on for a while so we know f of zero we know f of one equals one and then we just straight up like do this that's all it is because like that's it this works because we guarantee that when we're computing this we already know the previous answers and in general in this sort of like loop style dp what you need to make sure is that um yeah matrix exponentiation sure i'm not gonna i'm definitely not going over that right now but yeah that is an extra thing you can look into but the idea with this is that you just need to make sure increase the font size uh i suppose you just need to make sure that when you compute a value you already know the previous values that's all the ordering has to satisfy that when you compute a value you need to know the values that it depends on but other than that you can do it however you want okay now this is called pull dp where this answer sort of pulls from previous answers there's yet another way that you can do this and this is actually the way i prefer which is more which is called push dp and the way push dp works is you see that f of 2 relies on f of 1 and f of 0. but instead you can sort of reverse these conditions you can say that f 0 contributes to f 2. you can say that f 1 contributes to f 2 and contributes to f 3. you can say that f 2 contributes to f 3 and contributes to f 4 and so on personally i find this easy to work out it's based on preference basically but the way you would implement this is you still begin with the base cases but now you would go here um and you would say f of i actually we'll ignore zero because it's zero anyway so then f of i plus one plus equals f of i because f of 1 contributes to the next value and f of i plus 2 plus equals f of i because it also contributes to the second x value and then by the time we get to f of 2 we will have already processed all the things that contribute to it so in the same like by the same argument kind of we know f of 2 by the time we get to it so when we get to f of 2 we're allowed to push it out because we already know its answer so this is called push dp hi costa how are you doing are you tuning in for the the later breakage that's going to happen i do not have every monday off this is a specific monday that i do have off but usually i probably will stream on like wednesdays or something because that's also a day when i'm open it kind of just depends that's the reason you should join the discord because it's always going to be inconsistent like stuff is always happening that changes my schedule so yeah and the discord which is in the description like it's like right here you just open it right now it's right here you can um get notifications for everything so when things change you can still find them or you can also go to the community tab on my youtube either way on both of those places i'll be announcing streams and even on this code forces thing like right now you can see this stuff but yeah there's there's probably not going to be any sort of element of consistency i'm sorry about that anyway that is my intro to dp took about 20 minutes i don't know um yeah all right now we get into the problems are y'all ready to have your minds not blown but sewn i guess okay i am recording this youtube will automatically upload this as an archive later so that will be fine all right you have okay i've already read this but you have a given integer n find a number of ways to fill all three times n tiles with the shape described in the picture oh wait wait actually first uh time old tradition that always before starting i add my current subscriber count to my template and i've definitely explained this before but the ultimate goal with this is to try and get a memory limit exceeded verdict by having it take up so much memory that it crashes um i reckon it'll take about 9 million or so to do that so maybe next week we'll see all right you have a given integer n find the number of ways to fill all three times n tiles with the shape describing the picture below upon filling no empty spaces are allowed shapes cannot overlap right okay so um let's kind of just like think about what what can we do to this um we have this grid let's think of it uh wait figure out some way to draw this will i mod it back when it exceeds um maybe i actually don't know what i'll do hopefully by the time i get there code forces will have upgraded their systems and it'll be 512 megabytes or something so that it won't ever be a problem like i'm sure with the with the prowess of computing power um like the standard memory limits are going to be higher or something and then constraints will just have to be higher too because computers are going to be stronger i imagine i'm not actually sure how much farther we can take it but it should be pretty good at least okay so we have to fill all of the tiles with the shape ah this is barely visible is it we have to fill all of the tiles with the shape um let's do it like this which means like no matter what we do we have to put something in the top left corner right so there are um so there are like three different ways to put something in the top left corner we can do it like this this is one way we can do it like this or we can do it like this let's look at all of these cases what happens with this problem all right so here look at this like this is a problem because when we put this down what are we going to do about this cell there's no way we can put something down to fill this cell um wait it's like there's no way we can put something down to fill the cell because all of these are blocked by this so automatically we can't do this one we're blocked from putting this l-shape down so we have two other ones that we can do we can do this one and then what happens here now again look at this cell there's only one way we can fill this cell and it has to be something like this so if we put this one down we automatically have two um what is it like we automatically fill in two of the rows so this is one way to do it and the other way that's possible is this one but again look at this cell like look at the cells that are blocked off by when you do this how does putting this down affect the state it makes it so it's harder to put down other things and the only way to be able to fill the cell is by doing this so again when we put something down we cover the first two rows so there are two ways to do this we can do it like this or we can do it like this blue with blue and either way it fills in the first two rows so um the first thing is if we have an odd number of rows then there's no answer and otherwise well okay so the answer the answer you can think about it mathematically but this is a dp stream so i'm going to solve this with dynamic programming even though it's like kind of unintuitive let f n be the answer for a grid of n rows yeah it's just two to the n over two it's fine but i'm going to do it with dynamic programming so let f of n actually way okay okay let me i said that i said to her to the end of her two it's okay let me first like okay so all i've done is fibonacci right and so it's kind of like how do you apply this sort of concept to other things so there's a sort of strategy you can do to approach a dynamic programming problem there are a few things you need to know to be able to make it work you need to know um you need to know the state the state is what information are you carrying like what information are you storing answers for for example in fibonacci the state is just n that is we're storing the answer for a what the hell what just happened in chat uh okay i'm gonna trust that that mute was warranted so this essentially the way this works is we store the answer for a single number and that number is the only bit of information we need however we could have other states like we could have states that rely on two numbers for example in a grid one possible state could be the row and the column of a cell and so it's not able to just um i didn't see the messages by the way all i saw was that they were removed so i'm not exactly sure what happened but this is the way this works is it's just going to be it's going to be two numbers and really we can have a state be whatever we want it can be like 12 numbers if we want we could have i've i've solved the problem before that was six dimensional dynamic programming like it relies on six different numbers and this is like stupid but it's possible the state is the information that we need to maintain like and with this with the state you should be able to uniquely determine the answer so i'll kind of get into what that means later and what kind of states aren't enough information because some like the state has to represent the whole problem so there's also another thing you need to know the transitions for example in fibonacci the transition would be f of n is equal to f of n minus 1 minus now plus f minus 2. in certain problems this is the first problem on the mashup i'm doing the mashup in order so uh you can also find the mashup in the description right now yeah i know i'm not i'm reading chat for questions mostly i just saw that something weird happened and i was confused f of n is equal to f of m minus one plus f of n minus two so this this defines a way to find the answer for a given value based only on previous values this is a recurrence and um perks for spamming kailangan igm chad orr's will mean ban i think i think that's the best um i think that's the best reward for doing that yeah i can i can put the current problem on sure although you have to have access to the mashup so just click that link f of n is equal to f of minus 1 plus f of minus 2. so the way this works is this just defines a way to find the answer for this based on only the previous values and this is what dynamic programming needs because all we know are these previous values that we've computed right so there's um one or two more things depending on how you argue you also need for example base cases usually um for example we are given that f of zero equals zero and f of one equals one in most cases this is the only way to make this hap like we need base cases because otherwise like there's no end to the things we're computing if we didn't have these this definition of f of n would go into negative numbers and it would go down to negative infinity because we never stop we just keep relying on previous values but these previous values like don't exist yeah they do need base cases someone figure out if mikey should get mod i don't know yet so this is only in context of fibonacci um so anything i forgot i guess we'll figure out later but this is the basic overview if you can find all this information you can do a program with dynamic programming if there's no like plausible state that stores enough information to find the answer it probably isn't dynamic programming it just depends but you definitely like obviously you can't apply dynamic programming to everything how can you understand if a problem is dp or not that is a hard question it's kind of it's not really understanding if it's dp it asks like the way to determine if you can use dp is just to check if you can use dp like in terms of competitive programming you're allowed to try a lot of different solutions and see what will let you do the answer yeah part of it is experience part of it is other things yeah overlapping subproblems is also another way to think about it but the idea is just think about dp and then try and come up with this information and see if you can apply it and if you can't think of any plausible way to apply this a dynamic programming solution to it then it's probably not dp and you can think of something else it's not really necessary to try and like flag a problem as dp and then and only then think about it you can just think about every problem and try to solve it like a dynamic programming problem and if it works then it works and if it doesn't then you can try other strategies um dp makes sense until they like yeah harder dp comes with kind of experience you need to like there are a lot of tricks you can do with dp and oftentimes you just need to come across them in problems to be able to understand them it's way too many like things to um go over but anyway i'm going to explicitly go over this process for this problem the idea is for every two rows there are exactly two ways to tile it for every two rows there are two ways to tile it so let f n be the answer for n rows first of all there is one way to tile no rows you simply don't put anything in so the base case i'm going to use no queue now so the base case and yes i am drawing with a mouse by the way which is why the handwriting isn't perfect base case is f of zero is equal to one because the zero rows we have exactly one way to do it we just do nothing um okay the base case is this and then now we need well okay so this is the state right the only thing that matters is the number of rows we have we don't care about the column because we're filling in entire rows at once so the column is irrelevant all we care about is the rows so the state is f of n the base cases have a 0 equals 1 and then what happens here say we have four rows left well in one like move we have yeah that's a really good quote those who don't remember the pass they're condemned to repeat it in one move we can fill in two rows and we have two different ways to do it so think about what this would be in terms of f n the transition is we can fill in the row one way and then we we add f of n minus 2 because we fill in the row like this and now we're interested in the number of answers for two rows because now we don't care about these rows we've reduced the problem to having two fewer rows so if we fill in one way then we add f of minus to the answer we can also fill it in the other way which i will label as brown we can fill it in like this which is also plausible and then we fill it in the other way and then we add another f of minus 2. and the way you work this out is you basically think about when you have a problem where you're solving for n rows what can you do like what does the problem ask you to do in this case the problem asks you to fill in the tiles so just think about the ways you can fill in the tiles that's essentially the way this works you have two different ways to fill in tiles both of them remove two rows from the equation so you work with a problem with two fewer rows and both of them ask for the answer of having too few rows which is f of n minus two so we get the recurrence f of n is equal to one way we can do it is to add f minus two and the other way also add f adds f of n minus two so the recurrence finally is f of n equals two two times f of n minus two all right that's ugly um where did i learn dp uh it's um i think that's a good question actually i think it was used to go training that was my foundation for everything although it took me a long time to understand like if you're having trouble learning dp that's natural it took me months to get um but at the same time i think one of the problems was that i didn't have enough examples so all right okay so like i mean this is clearly optimizable but the whole point is that we're doing this with dynamic programming and this is it this is the recurrence we have um move this over all right we have our three things so let's do it but actually here wait let's apply the age-old trick of converting this into iterative dp yes this is for beginners let's apply the age old trick of converting this to interdp where we essentially we replace the parentheses with brackets and now we're working with arrays instead of this this is magic isn't it but now like we just straight up have a recurrence where we can do a raise with this so as long as by the time we compute f of n we know f of m minus 2 then we can find the answer for f of n which means it's equivalent to saying when we compute f m we want to know all previous values we want to do f of n after we do f of 0 to n minus 1 which means let's just compute f of increasing order so let's do it like this um yeah okay um that's true with f of one when you have exactly one row there's no way to do it because you can't put any tiles down to make it work so so yeah you're right sorry there are two base cases f of zero equals one and at the same time f of one is equal to zero because there's no way to do it if you have one so let's do this now um how does this work c into n um f n plus one we need to know the numbers from zero to n f of zero is equal to one f of one is equal to zero for i is two i up to n f of i is just two times f of i minus two and then we're done oftentimes once we compute this recurrence and we make all this work it's just like it's just nice see if it works hopefully it does we get four all right we've solved the first problem um i'm going to ideally not go as slow for all of these because it's going to take a long time but that's the idea so yeah procedurally find the state find the information you need to know find the base cases and find their currents and oftentimes it's a better idea to find the recurrence first because then the base cases are just like you need enough base cases so that you don't like recur infinitely which means at some point you have to stop so it helps to first know the recurrence so that you need to so that you know the values that um you need to stop and in fact even during this stream after i figured out the recurrence someone pointed out that i had the base case wrong and i needed more information so it's generally a good idea to first find the state and then find the recurrence that operates on the state and then find the base case that works with it yeah also base cases are kind of like the easiest part um because it's just like thinking about certain values and you can easily compute certain values i'll take specific requests after this match-up okay right so this is it this is all the code is we just straight up do it f of zero equals one because with zero rows we have exactly one way to fill in the rows validly like we just straight up do nothing and f of one is zero because with one row there's no way to do anything there's no way to fill in these things f of two equals two yeah that also works um in terms of a more intuitive base case you can define it like this and then f of one equals zero and not worry about f of zero like f of zero kind of represents the way to do it with zero rows but at the same time it's also just convenient implementation to define it as one like it's kind of the same actually no i'm not going to talk about math but like you can do whatever you want as long as in your implementation you get it right you can mess with things it's okay to do that as long as it's correct okay how can you come to the state well that's a good question it's kind of at the same time computing um like what is what is the problem asking this problem is asking given a grid with n rows or given a three times n grid specifically with n or n columns my bad what are the ways to tile it so this three is fixed the three really doesn't matter for the answer so the only like input value is that we have n rows so to solve a problem on n rows what can we do well we can try and reduce the number of rows and we can make it so we have the exact same problem only with fewer rows with other things you with other things at the same time you could just either they don't affect the answer or they do and if they affect the answer then you need to store them in the state so as an example um yes the input defines the state kind of this wasn't 40 minutes for a problem i spent like 20 minutes explaining the first um the first thing so if we had for example more than three rows like this three wasn't fixed we had for example um k rows and n columns then we might need to define the state differently we might need to define it as f n and k because now the number of columns is important it just depends on what the answer depends on and it's it's going to be hard to figure out the state that's like the hardest part i think with intuition and sort of relying on practice problems and like the problems you practice yeah f k n maybe either way like with sort of practice problems and previous problems and stuff like that you can get better at identifying what you need to store it's it's mostly intuition okay and fun fact there's a much simpler formula you can do than dynamic programming because people wanted that it's simply 2 to the n over two because for every two rows you have two ways to do it and the rows are independent of each other so it's just two times two times two and over two times right but there's no reason about that so that's another way to do it i'm just doing it specifically with dynamic programming okay anyway that was the first problem let's do the next one does not say i sold it i did solve it right okay all right now we get into um more serious problems i suppose you have a string consisting of n lowercase latin letters he decided to type all substrings of the string s um okay a substring of s is a non-empty string x equals s of a to b so like a contiguous group of characters um yeah but the keyboard is broken and therefore you can only use k different letters in the igm video i said don't stop keep trying things now i say i have to stop when did i say that um keyword is broken that namely you can use k latin letters out of 26. so you're interested in the number of substrings that you can still type using the broken keyboard okay and it's 20 and is 285 k is 26. yeah the mouse is loud i don't have a better way of drawing i am eventually getting a writing tablet eventually just not yet oh coach mode okay that makes sense i i'll just stay in coach mode then it's not really that big a deal oh oh that's what you meant okay yeah sure well that's not you stopping that's the program stopping that's different okay so let's um formally write this out abacaba is that how this works yeah do i have a pc2 and no it's just the wonder laptop uh facecam coming at 10 000 subscribers you guys could get me there you know it could happen it's all up to you guys now the first step for doing this is like the first step of attacking this problem is like what can we even type we can type any character that's valid that is we have it on our keyboard but like at the same time all these valid characters are kind of the same it doesn't matter yeah i have my water bottle with me it doesn't matter what the character is what really matters is if we can type it or not so let's reformulate the problem now we have a bunch of characters and let's define a character to be one if we can type it using the keyboard and zero if we can't so for this problem where we have abc avicaba and we have a and b as the possible ones um then all of these characters are going to be ones and the rest are going to be zeros and now um asking for the number of substrings that we can always type is equivalent to asking the number of substrings where everything is a one now there are many ways to do this you can do this with math i would prefer not to let's solve it a different way in these sorts of counting problems there's like this universal trick you should always try you should try to fix something that is say what i'm going to do here is i'm going to i came up with this kind of by intuition but the way to fix something is say i'm going to solve for this being the last character this c is going to be yeah i would use math for this but it's deep it's a dp stream so i kind of have to so um i'm going to i'm going to say that we're going to solve it for the number of k for the um strings that end at this character so the substring the end of this character the sub string is the end of this character and like how do you come up with this well you just kind of gotta try a lot of different things and one of the things you can possibly try to fix is a single end of the character so if i can compute if i can compute the answer for all substrings that end at this character like the number of substrings we can type that end here then we can sum all of those up and everything will be perfect there are many other things you can fix for example you can fix the um another thing to try is possibly the length of the substring you can say we're going to solve for all two things for all substrings of length two i will take suggestions later not right now we're going to say we're going to solve for all sub strings of length 2 and then maybe that'll work out who knows uh it doesn't work out here and one of the nice things to fix is the end of the string so let's do that now let f of i actually wait before i even do that now when we're solving for a specific end of the string what really matters well what matters is just the position we only care about where we are because we don't care about the beginning all we care about is the ending point and the ending point is a single point oh yeah current problem this is please remind me to do this i am absolutely going to forget um by the way this other link is for embed it's our program it's our um competition you might want to check it out it's like it's got stuff like we've had dp problems in the past so if you want to tell more dp you should check that okay i can't do this but it's it's prepared by myself and others so hopefully it'll be some level of quality if you like contests you should check it out okay okay okay let's get back to it i'm not can i pin stuff in chat do i have the option to do this i don't think i can oh we've definitely had dp in the past at least 2019 maybe not 2020. i do have to plug in bit yes it's kind of like contractual obligation wait how do i pin a message um i'll figure that out later maybe what do i have to do not sure oh wait like a comment or oh do you mean like a comment on the video or like a live stream chat live stream chat like i'm not sure how to do that this is all i see right now i see put user and timeout hide user add mod report and remove what do i have to do here like i know i can do it for comments i've done that before but it's not here or is it not sure what you mean um like these three dots who is conta indeed i'm not sure myself try to pin any random comment i'm not sure how to do this why is it that when i have why is it that when i'm struggling to do live stream stuff i have more viewers than actual problems like after i type it i have this and all it says for me is remove now working with the live stream isn't dp it's mp hard do i have plans to set a contest on cf i actually have kind of i've made i made this like testing round and it kind of just got ignored because it was a single blog and then like not many people checked it out but i do have a round that i wrote most of the problems are kind of lame but it exists if you want to see it you can find it in the gym okay i'll google how to pin a comment on live stream i can remove all other comments sure um okay i have this open on my phone right now we're figuring this out i suppose yeah i have more viewers than i what this is like dream getting like 80 000 viewers for a blank screen how do i pin a comment on my live chat oh wait it needs 100k to do that okay okay okay look it's saying online that like you need a certain number of subscribers to do it i don't know if it's possible like for me because i'm not that big in the youtube world yet but maybe later i don't know like i just i just don't have the option try popping out chat this work do i have anything better here i am not in college okay i don't know how to do this i'm just going to get back to the problem that is a good plan yeah i'm in high school right now i did try printing my own comments like if i do this it just says remove and then that's all i have i can't do anything with it okay i kind of like have to re-explain this now since we got so off track so you you're given a string you're given a certain set of characters you can type you want to find out how many sub-strings exist where you can type all of the characters so we define a so we define a problem don't we have enough mods already i think it's fine right now like there's not much to moderate click on manage moderators then remove niche chat yeah i've been wanting to do that for a while actually okay so we define this to be a one we define it to be yeah we just find this to be a one if and only if we can type it can we use bit masking after converting to zero one well i wouldn't say that it's kind of like i don't think that's possible no i'm 17 right now so what i was saying was let's fix the right endpoint of the string so let's say f of i is equal to um the number of strings or the number of substrings f of i i wanted to pin comments so i could um have this exist as i could have the current problem pinned and so it wouldn't be as weird to see but let's define f of i to be the number of substrings that end at i that is to say no that's just what it is the number of substrings that are all that consist of only ones that end at i what should i make you mod for i need job and becoming mod is big on resume well i'm sorry if you're not being hired today then so um let's say we're solving for this character and so the first you can find the problem here if you want to read it mod you are you get the again i thought you were taking the donut anyway so we're here yeah the chat is very distracting i agree so we're here so if this character is a one then um if this character is a one then actually let's say like this if this character is a zero then like no matter what i is a zero so there's no way we can have a string ending at i that has only ones because like we we already don't have a one automatically i is not one so instead now we assume f so automatically if um let's define this as array a then if a i equals zero f of i is equal to zero before we continue can we extend this to a subsequence and not it's not necessarily contiguous well if it's not contiguous then it would just be the number of characters validly and we can have we can either have them or we don't so it'd be like two to the number of ones like minus one possibly that would be the answer it wouldn't be necessary to do dp here but so ai equals zero implies that f of i equals zero otherwise we assume that ai equals one because it's the only other possibility then what happens well first we have this we have the string consisting of only ai so automatically we have at least one but then also like what about the other substrings well all the other substrings that are going to be attached to this one have to end at the previous character now that's cool isn't it because like now we're just interested in what ends at the previous character and well we're interested in the number of strings that have only one that end at the previous character so that we can extend them by one and include this character but like by definition that's f of i minus 1. it's the number of substrings of only ones that end at the previous character so the recurrence would be f of i is equal to the number of substrings we can extend plus this character itself because that wouldn't be included previously so plus one and then the answer is over all possible ending points how many substrings do we have which is essentially saying it's the sum over all f of i and the base case is simply for a string of length zero for a string of length 0 we have no ways to do it we have no substrings because there are no strings at all so then we can define it like this actually i'm going to write this in red or something um bit mass bit masks yes i do have a plan for that actually i think the next problem is bit mask i kind of like hand pick that one right state recurrence base case we're done that's it so let's do it um we have n and k and then we have the string um and then we're going to just define a okay well it's it's a it's a um it's a very like weird kind of bit mass dp dp on trees i don't think we do maybe i can i can do that after the stream possibly i'll try and find stuff like that but let's just store instead of like storing the number of typable characters we can instead store an array for each character and check if that character is typeable or not that's true an array is a degenerate case of a tree i guess um and then we say automatically just defaults to zero so then and then we read in a character and now it's on the keyboard so we defined it as typable and this subtracting a just means that we normalize it to the numbers 0 25 instead of that's what this does so now what we can do is we can reformulate it we can create this array a that's one if a character is typable and zero if not um if typable s i minus a a i is equal to one else a i is equal to zero and of course you can get rid of the if condition do like ternary stuff doesn't matter uh i don't have school today specifically i normally do have schools on monday school on mondays because this was like the end of the marking period or something right now let's define the function this is the dp function and the base case is that f of 0 is 0 which we define then then we use this so if a i is equal to zero then our current says that f of i is equal to zero except we one index this so therefore we need to add to i plus one not specifically i and otherwise f of i plus one is equal to as their current states f of i plus one then the answer is the sum so let's do that too and that'll be it i'm really glad you can't clip this on youtube i'm really glad you can't make clips on youtube because i'm sure there will be so many of me struggling to pin a comment it would be sad you know part of the nice thing about youtube is that because i've flushed the solution out so much it has a really high chance of like just being right on the first go so sometimes it's an idea to like think out a solution really hard before just blindly going at it um you can use dpa instead of recursion always not necessarily it depends on like the idea of dp is remembering previous answers so if you have like if you have like 10 to the 18th previous answers like for example it depends on an array element or something then that may not necessarily be possible um well it's not necessarily a session because this this whole live stream is going to be available on my youtube channel after it's done so even if you missed part of it it'll still be here also i intend to go through these later problems quicker we just got very distracted here but the idea of dp is remembering previous states so if there's nothing to remember for example if every state you visit is different there's no reason to use dp like it's not going to help that's just where it applies okay um onto the next one yeah this is where the bit masks comes in bitmask comes in um current problem is updated just gonna highlight that okay berlin shop sells any kinds of juices each juice has its price each juice includes some set of vitamins there are three types of vitamins vitamin a vitamin b and vitamin c each juice can contain one two or all three types um future 1v1 lockout with second thread that is a possibility kind of depends on things i do see that as a possibility it could happen in the future um yeah collaborations are possible too there are also a lot of other channels that are starting up that um are doing tutorials for example this one guy algorithms conquered is one that i've looked at before so that's you can check him out there are also other ones but yeah i'm sure collaborations are possible in the future we'll just have to set things up is knapsack dp yes it is a form of dp is fft dp i don't know fft but probably not i don't think it is all right so each juice can contain one two or all three types we need to get juices so that we can have all three vitamins is greedy dp generally not sometimes generally not so what is the minimum total price so that you can get all three vitamins all right now this one is kind of messier because the state isn't so simple now let's say we have some function f of x wait let me scroll up let's say we have some function f of x actually i'm just going to say this is problem c let's say we have some function f of x where x is the state that we're trying to find the answer for is tpdp yeah no it's not but like what is x well what we want to know is how what's the cost for obtaining all three vitamins right and these vitamins have no relation to each other so the way it works is like what can we do here in in some sort of state we need to have it so we have information on the contest is restricted yeah um to open this problem first you have to click the first link so that you can be invited and then you can open the specific problem i'll put that there so we need to store if we have the vitamins or not this difficulty is 1200. so in a state we need to know do we have the a vitamin do we have the b vitamin and do we have the c vitamin and specifically we can store it like this this is a zero if we don't have it or a one if we do this is a zero if we don't have it or a one if we do this is a zero if we don't have it and one if we do so there are two ways we can represent this we can do it like this we can make it three variables and we say that this represents if we have an a or not this represents if we have a b or not this represents if we have a c or not and that's like one way to do it but there are other ways to do it too instead of doing that we can compress all of these three into a single number because notice this is a this is either zero and one this is also either i'm doing problem c this is also either zero one and this is also either zero one this is binary isn't that cool we're interested in the binary state of whether we have an air now whether we have a b or not whether we ever see or not but like i think just think about computers like computers do things in binary we use numbers in binary so why don't we make this whole thing just a single binary number let's have three digits the first digit is a the second digit is b the third digit is c this first digit represents do we have an a or not the second digit represents do we have a b or not and this third digit represents do we have a c or not so a has the value of 2 to the two to the squared which is four b has the value of two to the one which is two and c has the value of two to the zero which is one we're doing problem c i'm gonna i'm gonna like do this now i'm gonna write the thing at the top and we compress this binary sequence into a single number that represents all of them at once this is called a bit mask it's a mask of bits compressed into a single number that represents the state we want and this is more generally known as bit mask dp we ask we have a recurrent we have a state f of mask that basically says what is the minimum cost to have it so we've satisfied everything that the mask says we have so for example if the mask is 1 0 1 which is equal to 5 then we have to have satisfied that we have an a and we have a c uh why is it called rolling i don't think you can super chat i don't have um i'm not a partner yet which i haven't even applied yet i probably should do that at some point but i don't have any sort of setup for that so f of mask represents lowest cost to satisfy the mask [Music] we can also introduce another state this this is sort of an implementation thing however you want and mask which is defined to be the lowest cost lowest cost to satisfy the mask where you've only used the first n strings this is generally how dp would be done because you're going through the strings in order you can actually abstract out this part and just kind of get rid of it it'll be implicit but this is the explicit definition of how to do this it's the app it's the lowest cost to satisfy the mask using the first end string oh where did these numbers come from this is just how binary works the first thing takes the position of one the second thing takes the position of two the third thing takes the position of four etcetera like it's just a binary number that's all we're doing here we're com we're converting these zeros and ones into a single binary number and it's convenient because computers work in binary yeah it's also representing kind of a set of objects and then the bitwise operations do some cool things let's go with this so f of n mask is the lowest cost using the first n strings all right how do we do this sort of recurrence um this is where i prefer to use push dp so i'm going to kind of describe how to use push dp right now yeah three variable truth table sure so what does f of i mask contribute to so the transition for f of i mask will be considering the i plus one string and what we can do is we can represent these strings also as a bit mask we represent the string as a separate bit mask which asks do we have an a in this string do we have a b in this string and do we have a c in this string and we do it the same way this is two to the two this is two to the one this is two to the zero and then we'll call this mask m or something so we have a mask for the state and we have a separate mask for the string and somehow we have to combine it so the transition is either we either we don't take string i plus one in which case we just still have f of i plus 1 mask because we've considered the first i plus 1 strings and we just don't use it this time so that's fine or we do use it in which case we have to consider what happens so this this is f of i plus one because we now consider the i plus one strings but what happens here well there are this is where the truth table comes in so this is you can sort of bash out the way to do this transition like this we can say we had before we might have had it before in which case we don't care about whether we have it here or we do have it here in which case we don't care about whether we had it before right so there are four cases either we had in both of them we had it before but not here we had it here but not before or we haven't in neither and well this is just asking like if we have it in at least one of them we have it no matter what so this is bitwise or you're going to bit wise or the masks together because if you have the bit in at least one of them then you're gonna have it afterwards so it's mask logical or m and the cost for this is the cost of taking string i plus 1. so you would have to consider f of i mask plus the cost for that one the base case is simply we have zero strings and obviously we can't have anything satisfied so it's zero because we don't have any costs either so now let's do that this binary number is just the number between zero and seven so we can represent it in array of size eight first we need number n and then we can make this array of size n n plus 1 and 8. then we can do this by checking um so we want to make it so if we can't get to a state then like we want to make it so we're never incentivized to use that state one way to do this is just to initialize everything to infinity because that's the highest possible cost we can have and therefore we'll never want to use it so let's define infinity to be some huge number like 10 to the 17th which we'll never get to in the cost because the costs are just 10 to the fifth then f of i and j is simply infinity this also gives us a convenient way to check if we can't have it at all because if we never reach the state we if we never reach any state then we're like totally fine so we also define the answer to be infinity and then we say cost string s so now yeah if you um watch it later and leave a comment i'll try to answer int string mask equals zero so for ins um like this is the position in the mask i'm going to stick with this notation of representing a c c is the first digit b is the second a is the third so this has the power of 2 to the 0 power of 2 to the 1 power 2 to the 2. so the corresponding character is this minus the position so in the first position this will be a c second will be a b third would be a let me just go through the string and see if we have it then if we have it string mask plus equals um one left shifted by pause which is the same as saying two to the position okay there's a possibility live subtitles i could try that i'm not sure if that's possible wait what is this if your video doesn't require closed captions it should be like automatic if it doesn't i guess it'll have them after wait can you are you able to enable them i guess you can't it's kind of annoying yeah i guess it's not possible live sorry about that um we'll have to figure that out later i'm not trying to do that okay let me um finish this off so for a certain value of i we just like iterate through all the possible values and masks which is zero to seven and then we find what it pushes to so um the first case is that we take nothing and therefore we just do this so f i plus one mask it's just the same thing equals min f of i plus one mask um f i and mask that's the first case and the second case is we do the same thing but we do take it so f of i plus one mask bitwise ored with string mask equals min spawn mask bitwise or string mask plus the cost of taking this string which is cost and then the answer is any possible way to the answer is the minimum cost having considered all of the strings of having the full mask of a b and c so the answer is um we define it here f of n and 7 because 7 is the number that represents having all of the bits enabled if the answer is infinity then we never reached it and therefore we want to print negative 1. and that's how this works this is bitmassdp in a sense what [Music] um no matching up um f i mask and it breaks nice uh cool oh because i never right we want the base case setting this to zero as we define here fifteen this should be negative one we have no answer should be thirteen should be two fifty it should be 16. okay by the way in the time that i have for the stream i don't expect to get through all of these that's not the point the point is that like we um the point is that we just i don't know i'm trying to be elaborate here and trying to explain everything and yeah it's the point is not speed that's what i'm saying kind of lost my train of thought multiple times we do get the problem dude okay yeah there is no reason to spam a question six times i will try and read all the chat and if i don't you don't have to like keep saying it but um practice div twos probably i'm not sure that's kind of the way to go yeah don't spam that's just annoying the time i will only last five minutes to be able to talk more later so this is just d i don't even have to change the link every time it's just problem d um yeah let me read the rest of the chat i may have missed things from where can i practice number theory i think you can that should be a tag go to problem set and then um add tag and then number theory and here you go you can also pick difficulties if you want like 2400 to 3500 which i'm not going to do but but you can do whatever you want coforces is pretty nice these are all 1200s um the first the way this distribution works is the first is a thousand the next three or twelve hundred and then the rest are randomly distributed between fourteen hundred and two thousand so some of these are are possibly quite hard your friend mishka and you attend a calculus lecture scared of saying names lecture there's so many ways to mispronounce something lecture lasts and minutes he tells ai theorems during the eighth minute um it's really interesting calculus but it's hard to stay awake you're given the right t of music's behavior mishka is asleep during the eighth minute of the lecture then ti will be equal to zero otherwise it'll be equal to one which goes away he writes down all the theorems he's being told otherwise he writes them you can keep them awake for k minutes straight you can only use it once you can start using it at any valid minute that would like work sure your task is to calculate the maximum number of theorems you'll be able to write down if you use your technique only once so wake him up um watch your competitive programming journey video i mean you could take the same route it's not necessarily necessary there are a lot of ways to get good but i'm not sure i think just like the like the a general good rule of thumb is practice whatever you want to be good at so if you want to be like 12 000 rating on code forces you can do a lot of code forces problems because that will tell you exactly what you have to be able to do to get 12 000 rating on code forces okay why is this dp that's a good question well you can think of it like this practice juggling later i'm doing that today i said it i'm doing it today i'm doing it today i hope i hope all right okay so here's the idea let's think about this problem like this one three five two five four now this is dp like a certain sense of the word it's not entire well actually no it is dp for sure so this is one one zero one zero zero and the way this works is you wanna pick a range and then automatically you're going to get all the numbers in this range but at the same time you're also going to get all the numbers in this range where you have a one but not the numbers where you have a zero um right so let's do it like this let's say we pick an arbitrary range then what we're interested in is three things the sum without like modifying the numbers of this the sum without modifying the numbers of this and the sum of all of the numbers in this okay now there's like a cool way to do this and and not cool way to do this i'm probably finding the not cool so here's the idea um the idea does indeed exist right so we're interested in is the like normal sum of this so let's break this into three parts right we want the unaffected sum of this prefix of the array we want the unaffected sum of the suffix of the array and we want the total sum of this so in terms of dynamic programming it's like it's still building off of previous answers let p of i be the unaffected sum of the prefix okay so um any prefix will consist of two parts you can think of it like this it's the last element and everything else so this red part is the range corresponding to p of i and this orange part conveniently corresponds to p of i minus one since it's everything but the element you just took which is the same as the previous prefix so p of i is equal to a of i whatever a of i may be this could be zero if the value is zero or something greater greater than zero otherwise plus p of i minus 1. this is in some sense dynamic programming and we can do the exact same thing for the suffix s of i is the unaffected sum of the suffix actually let's say it's the suffix of the last i characters because that's kind of convenient actually is it no it's not let's say um it's the sum unaffected sum of the suffix from i to n and then we're just kind of interested in that and then the formula is basically the same we draw the same diagram this is the part we include this is everything else so this is s of i and this is s of i plus one so s of i is equal to a of i plus s of i plus one okay now that's that's these two parts what about the middle part isn't that fun well the idea is this is a thing why are you spamming dots is this morse code i can't read morse code is someone fluent enough in morse code to understand this or is it just nothing that's just nothing then that's annoying but ah yeah i guess you can mute i don't see the point with that mashup will be active yeah everything like this whole stream everything is going to be available afterwards so uh you can find the problem first click this link and then you can click this specifically everything will be in the description um but yeah everything the mash up the video all of it's going to be afterwards it's like it's going to be available afterwards okay now this is a cool thing called prefix sums we're interested in the sum of not the unaffected sum but the sum of all of the array elements so let's do it like this it's we let prefix of i be the sum of the first eye elements not the unaffected sum but the sum of the first i elements specifically then it's the same recurrence as p of i i'll do it in green prefix sound like my math teacher prefix of i is equal to a i plus prefix of i minus one and the way this works is what we want to do is we want to use this to get the sum of anything get the sum of any range so let's consider some range we have in the array but we want to represent it as sort of this prefix thing so let's consider the whole prefix that ends at the end of this range okay but like look look man we got this like gap here right what we're interested in is this and we have all we know is this so what if we just like we do this but we take out this gap and then we just we're just left with the thing we care about right so this gap on this range l and r this gap is the prefix of l minus one elements and then this gap is the prefix of r so to get the sum on lr we just take the whole thing and then subtract out the stuff we don't want so it's prefix of r minus the prefix i'm capitalizing l so it doesn't also look like a one minus the prefix of minus one and that's how you would get the sum on a specific range this is more commonly known as prefix sums but it's like it's it's a form of dp so it still counts i would suppose i think that's why i was tagged that so now let's do this let's just like this is going to be tedious and there are smoother ways to do this but i'm doing this explicitly because it's like just nice [Applause] so then we use ai to represent the first array bi to represent the second array and we can think about it like this so um i'll just define it explicitly so the base case here would be that well there is no p of negative one so you have to define p of zero explicitly and p of zero is just a of 0 so we can think of it like that p of 0 is equal to a of 0 times b of 0. this is convenient because if it's a 0 we don't want to count it and if it's a 1 we do want to count it so if we just multiply it's going to work out then we can do the recurrence um p of i is equal to a of i times b of i plus p of i minus 1. do the same thing for suffix i'm going in order yeah but the general idea here is that once we're here um the way this will work is cadenza i'm not sure how that would apply it's like a fixed range subarray we can do the same thing except for computing prefix sums i usually have a specific trick where i instead of doing the array explicitly i um like i store a variable that represents this and then it's not a recurrence anymore it's sort of like like you just maintain this variable that represents the suffix as you go along i'm not going for eight hours now um r plus equals a i times bi and you can do it like this and that makes it so you don't have some sort of edge case or anything and we can do the prefix sums isn't this font size enough i can't zoom in that much farther like it just kind of gets awkward this is the quality you can also um improve the quality of the video i think but the way this would work would be i want to find the best so let's fix the start point of the interval we're using um i plus k minus 1 is less than n because that's the end of the interval and then now we say we're going to do this on this whole array we take this interval this is i the end of this is i plus k minus 1 which means that this interval is the suffix i plus k and this interval is the suffix i minus one or the prefix of i minus one so um current equals zero if i is greater than zero the curve plus equals the like the p value of i minus one if i plus k is less than n we do the same thing i plus k and the way i do this is just simply this we consider the prefix of r if necessary we subtract out the previous one and now we consider it as the answer what asmr all i'm doing is typing i guess that works though this exists it does indeed so we just like compute these three things and then combine them i said this wouldn't be smooth and it's not but it's a way to like force it to be dynamic programming that's kind of what i'm trying to do here okay we're on to e it looks like this has a fewer solves than normal so that sounds fun let's do this there are n people in keys in a straight line every person wants to get to the office which is located on the line as well to do that he needs to reach some point with the key take the key and then go to the office what is the shortest time i've finished this a co-force contest that is a good question um yeah you can also do freebies on zero that's true officially i think it was like 40 minutes or something in some div three don't exactly remember so then you need some reach point with a key take the key and then go to the office in order to determine the minimum people need it for n keys okay so uh you let's think about this um you have a bunch of people ideally i will try and go a bit faster through these you have a bunch of people um each person is located on some point let's think of it like this and you have a bunch of keys um keys are going to be also somewhere yeah william lynn is pretty fast i would agree and the way this is going to work is every person is going to every person is going to take a key oh and there's also some office somewhere i suppose that's how this works and every person is going to take a path that first goes to a key and then goes from that key to the office oh yeah that div 4 it took me 37 minutes i guess that would be it although i didn't mind you read a problem and don't get an idea try to get more ideas like if you don't get an idea instantly that's normal generally you prom hard problems take a while to even think of anything but then as you think more and more about it stuff will become more clear for example you can find some observations or things it is a possibility [Music] um yeah he's very fast i would agree i took a while on kickstart g because i like am bad well problem c was like a pain okay so the basic idea for this problem is and i only came up with this so quickly because i've seen it before but like you don't the trick here is you don't want the crossed paths so consider some i'm going to move this down consider something like this well first of all you're going to assign every person to a key so we can think of it like this where we just kind of draw out this assignment right and then this person will go over here for example what to do if you're stuck in new being co-forces well that depends how effective is your practicing if it's not working you probably want to try something else i suppose you want to see what's working what isn't and i'm not sure improving is just kind of like a random thing you just gotta like throw yourself at problems and be better at thinking and the only way to do that is to have the experience i'm not i don't think it has a greedy solution there's no guarantee that the greeting would oh come on you've been knew me for like three weeks there's no way that the greedy solution would be guaranteed to work um wait i'm gonna draw this here so now let's consider this these paths are crossed so like the idea is that we don't want to cross these because consider this um consider it like this let me figure out some way to illustrate this that isn't sure if you if you have a greatest solution is possible with greedy but i don't think it works that's the thing so you have an assignment like this but like i claim that this green assignment is always going to be better that if you have two paths where this is less than this and this is less than this but this is assigned to something later than this then it's not optimal and this is just like well known i mean the way to prove this could be something like this where it could possibly um you could possibly do out the case work like you can do out this sort of case work and realize that in every possible case the green assignment is going to be better but this is just true like this is an idea that is always going to seven streams for a single contest what the yeah basically this green thing is going to be better let me try and figure out some like non-annoying way to prove this because they're like if you do all the cases where like like for example the blue points can be between the reds or they can be on one side or the other side there are a lot of cases that you can all work out and they're all going to say the same thing that this green path that's green assignment where if you don't cross the paths is going to be better but that's the idea which basically means that the assignments of the keys you do are going to be in increasing order so you have the numbers one two three and four and you have five possible slots then it's going to be something like this like for example this would be the assignment but you can't cross them so you wouldn't have something like this every like assignment number will be less than the next one why am i saying this so elaborately because what it means is you can automatically assume when you've assigned the third person that you've already assigned everything before that third person and we're trying to do dp here right we're trying to get some sort of reasonable state that represents everything we need to know for the problem and i've just shown that the only thing we need to know for the problem is the last person we assigned so that's cool right and also the position at where we like the position we're at and the last person we assigned so if we were to write some dp based off this it would be dp of position and last person that would be it that's the only information we need to know because with this information we can uniquely determine like the answer and the problem we're solving and everything but you see how this wouldn't work if we can do them in any order because it's not enough to just say that we put down three last because now like what if we put down one or two afterwards it doesn't say anything all we know is that we put down three but in this problem specifically putting down three implies that we put everything down and it also implies that the next person we're going to put down is going to be four so just off this information we know everything and that's why dp works here um yeah again i'm not exactly sure how to prove this sort of lemon-like thing but that's how it would work and also notice that the cost for going to the office doesn't like change when you do this because either way you still use the same set of keys so dp position last is the minimum cost to have it so you're at at position yeah you could use bitmaster if the ordering wasn't so fixed that would be a example of bit mass dp i guess but yeah you would have two to the end states and that's just not gonna work um how did you do this so this is the minimum cost to be at this position and have used the um first the la like you've used this many people already then the answer is the maximum overall um is the maximum let me see the way to recover the answer is just the maximum overall j of our maximum overall i i suppose of dp of i and the number of people you have which is n because that's just the way it is like it doesn't matter the final position all that matters is that you've used all n people okay how do we compute this well um let's see to push dp or to not push dp that would be the question supposed oh yeah right whoops sorry the minimum you're right you're right you're right whoops it's okay i would have gotten through the sample and realized that didn't make sense eventually but yeah it should be the minimum whoops so the reason i find push dp so intuitive is because it uses the problem statement with push dp the transition is either you assign a person to here in which case you get a new state based on that assignment or you don't that's why i think pushdp is so nice because you don't have to like reverse the transitions to figure out how things works jenna how things work generally push dp is where you um you explicitly use this state and like kind of push its value out to future states like pause plus one last plus one oh my god that ham running yeah jesus but like that's the idea you use the state to um push out that value to future states i think that's the easiest way to do this so dp pause lasts you have two transitions either you take this one or you don't if you do you end up with position plus one and now you use the new person or this is problem e on my mashup which you can find in the description or you don't take it in which case you have pause plus one but the last value is still the same the base case here would be that it would be dp of zero and zero that's true indexing is indexing is very nice with push dp i agree dpf 0 and 0 will be defined as 0 and everything else will be equal to infinity because like we we don't want to accidentally for example say that we're we're at position zero but we've used one person because that could lead to an answer that is like not good so we want to initialize everything to infinity to make sure we don't accidentally like see states that don't exist or something but this is the idea we're going to assign things in increasing order so we can do dp it's kind of like it's a bit like the dp from like what would it be like the actually no it's not nevermind it's it like resembles longest common subsequence but it isn't okay let's read in the values llp so read that in um and then we do that and then we read in the first k values and we want to sort them because otherwise the ordering we do wouldn't make sense we want to make it so they're sorted in increasing order or non-decreasing then we define dp as follows we have n plus we have k plus one possible positions to be in because zero is kind of like a non-existent position and same for this this is like non-existent amount of people and we have n plus one possibilities for the number of people we get we can be within the range of zero to n so we do this stuff um dpi j equals infinity that works right um 1 10 to the 17th is big enough yeah so now let's go through i equals 0 is less than or equal to k i didn't even workout transitioned yet nice oh yeah yeah we did we did so either we take this and then we get the cost of adding this person or we don't take it and then we have nothing so um first we don't take the person then it's just dp i would welcome you but i don't know how to pronounce your name still so i can't i plus one j is equal to min dp i plus 1 j dpi j if this is infinity itself then we just kind of ignore it because it's like the minimum infinity and infinity and then we do take person this is only possible if we're not on the last person already so if j is less than n then dp pi i plus one j plus one equals min dp i plus one j plus one dp i difference between dp and k and kn well it's just kind of like it's just the array size what really matters is how you define it and i define it to be we're at this position and we've used this many people and so we have and we have zero to n like the possibilities for people are zero to n the possibilities for positions are zero decay so that's just kind of how it works push dp is what i'm doing right now it's essentially the idea that instead of having dp recurrences rely on previous states you instead use previous states to like push them out to future states which is what i'm doing kind of so this would be rely on dpij plus the cost which is no not really i mean it's kind of the same like you can just study whatever works for you and it's almost universally going to be fine like there are there's a very very small amount of problems where like a certain kind is necessary in general both push and pull dp will both work so this is dpi plus one j plus one dpij plus um the cost would be let's see it would be the cost between um it would be a j the j person minus b j this is the distance between them and then it's the distance between that key location and the position of the the position of the um yeah push dp is more of a style choice than a concept like it's not different it's still dp dp series next i can cover maybe i can cover the act code and like the accredited dps thing in like a different video or something yeah we can also define it to be like dp we can also define it to be dp i'm gonna do this in different color like for example dp of i j is like the minimum of dp of i minus 1 j minus 1 plus cost and then dp of i minus 1 j this is a possibility too i just prefer to do push dp like this i i mean i prefer to do push dp because i feel it easier yeah i'm not sure where the timestamp is it's like near the very beginning like before the 20-minute mark i think so this is the same idea we have to add the cost here so this is the cost of taking the person and then um well actually for this we don't even need the minimum because no matter what like what what we really care about is dp of k and n because any answer we would have already had before we'll continue to have it later on so k is fine and we need to have n people no matter what so so that's like what we need to do yeah dp okay and the fact that this is infinity doesn't matter because no matter what we'll reach this anyway so now we get 50. i hope or we don't did i do max instead of min nope i did not do the base case once again i made this mistake before and now i made it again where we explicitly define dp of zero and zero to be zero oh wait someone asked in my blog or a different blog so we get 100 what did i do the costume 20 should go to 40. 100 should go to 80. oh it's the oh okay okay it's the it's not the sum of times it's the maximum used time oh i misread that okay in that case it doesn't change much then instead of this being plus cost it's the um you consider it as the maximum of dp i j and the cost don't get why it's a hundred either this is still wrong it feels still wrong wait how do we get a hundred okay something's still up with this um and the idea is that what 11 to 15 to 10 11 to 17 what am i doing definitely missing something oh wait whoops this should be i my bad yeah we're taking the ice person and this error doesn't actually make sense but i do sort them both oh that's another mistake sort this up to the actual value not the previous one i'm sure there'll be more such mistakes in the future 69 years nice um my cofor's handle is galen underscore colin can find that it's just my name but like last underscore first let's see we read the values in we sort this by n we sort this by k do the infinity and put everything to infinity make this 0 iterate that to not k iterate this to n um don't take the person or we do take the person and then the cost is the maximum of this and the time it takes for this person because it's just how the problem defines it it's the maximum person any maximum time anyone takes and then the answer is dpkn yeah okay looks right submit first think later nice okay so we do have wrong answer on test five that's interesting in that case what have i done is 2017 big enough should be um oh no this should be this i think is that yeah okay because the i is the my position i'm bad more indexing errors yeah it's more of a typo than anything else i just kind of like didn't think like you know you have those like brain typos where you just totally gloss over something stupid okay um all right so that was e before we move on to f i'm going to uh grab some more water because the more hydrated you are the better of a thinker you are so what i'm going to do is i'm going to paste on a picture of a water bottle here so that you all may boost your own ratings and uh yeah i'll be right back i return i did leave myself a note to mute the mic okay let me um rechat make sure i didn't miss anything important um well it wasn't a stick it wasn't a stick actually what i did was i just i cropped this part but i cropped it badly so it was like this black part um let's see if dp is mysterious and confusing look down how to do top down dp because it's brute force of memorization yes i do agree with that that's like that is a very good way to think about dp especially for beginners because it's straight up just you remember the answers you already know that's the whole idea of it it's a great way to think about it especially if it's a new concept to you she's just saying how my viewership goes up when i'm not doing anything and then it goes down when i do do things this is like a very weird dynamic of streaming you guys can hear me right i've been talking at nothing for the past couple of minutes i hope not sanity check can you guys hear me let me check myself okay a permutation p of size n is an array i should just ghost the string yes i am 17. that is correct permutation p of size n is an array such that every integer from one to n occurs exactly once in this array let's call permutation almost identity permutation if they're at least wait oh okay almost at any permutation if there exists at least n minus k indices such that p i is equal to i your task is to count the number of almost identity permutations for given numbers n and k n is up to a thousand decays up to four which is interesting oh this is problem f i should update that so the way this works is like um whoa demoralizer in the chat how are you doing yeah i do kind of have a t i do kind of have a deep voice that is fair so the way this statement works is like consider some array of length n for example n equals seven and you got some stuff like just consider the positions a permutation is like any array so that every number from one to n occurs exactly once so it's like 2 5 4 3 1 6 7 would work as a permutation but if i replace this 7 with a 2 it wouldn't work because then 2 would occur more than once and 7 would not occur once so everything has to be the same thing okay um that's what a permutation is and an identity form an identity permutation is defined to be a permutation where every number is equal to its index so they they say an almost identity permutation is an identity permutation but three or four of these elements can but up to k of these elements can be out of order um was this annoying casework i don't wanna i don't i don't like that wouldn't like if it's annoying casework um yeah almost like an interpretation is for example this element can be something else such as six which would force this element to be something else because now you can't have the six be there i personally am from the us by the way um sure a lot of you are from india that's what my analytic says like the vast majority of my viewers are from india which is why i'm streaming at this time which is sort of inconvenient for people in the us but it works for most time zones um right so if we have an almost identity permutation the way this works is like if we displace some element then that means that this can't be a six anymore which means it has to be something else so either it's a four or it isn't and let's see why does that be four that's not fun yeah it would be casework it would be some stuff like cycles i have not been to ioi now i i can i actually haven't even made the i haven't made camp yet i can try i'm trying this here yeah these problems are random so either this is like a four you continue it but basically the way a permutation works is that it can be decomposed into cycles where for example say you swap these two elements then if you follow this element like say you start here and if you follow this element you're going to end up here and if you take some sequence of like going here you'll eventually be able to come back to this element and that's where you get a cycle most of these cycles are going to be here where you just like go here and then back to it um wait who are you talking about i definitely don't practice six hours a day you mean demoralizer he's pretty good very good um if a kid with age 18 goes to college can you participate in icpc i don't really know the rules for that i haven't looked because i i myself will be 18 when i do go to college i don't like this problem if m was three if m was three then there would be only one cycle but the issue with n being or k being four means you can have two separate cycles and that's slightly annoying um so i don't actually know what's up with that all right what does this mean all right most of the elements are equivalent yeah i know there's like why is this tag dp that's my question why is this tag dp because i don't see it i don't see a solution with dp well actually arbitrary k would just be like selecting um selecting some number of integers greater than one that's some decay and that would be annoying but it would be possible i suppose i don't see how to do this with dp does anyone does anyone in the audience actually know a dp solution because there's a way to do it with math and that's fine but oh is it like number of derangements how'd this work the arrangement has a permutation that has no fixed points oh i guess okay and choose k would be dp that's true okay that's they count factorial is dp fine oh no okay okay the six hour thing that's definitely not current i i practice like way less now in fact most of my practicing is just the videos i make but um okay i also said that six hours was an upper bound it was not six hours every day six hours was like maybe weekends where i didn't have much homework and i had a lot of time on my hands and i just spent all of it thinking about problems but that was not the norm maybe i did not make that clear when i said it yeah six hours a day would be insane you'd reach right in like less than a around a year or something like that if you tried that hard no i wasn't in the ioi team at all i'm gonna eat something because my jaw is starting to hurt from talking so much so well in terms of dp i actually don't know how to do it but there is a mathematical solution yeah i was not on the ioi team at all i don't i'm not sure if i have good chances of making it this year because despite my rating being high in terms of like used to go like the competitors like yusuko is not no it's like my it's like i'm exercising my jaw because it's just it's talking i don't know i don't know maybe it doesn't help i did say i'm practicing six hours dad now i'm pretty sure i would be an upper bound okay yeah so at least m is k indices where that are in order means that they're at most k indices out of order so there are four cases for k let's fix k we're interested in less than equal to k but let's just fix a number x let's just fix the number x so that um like in x positions this is not equal to this what gave me the motivation to start a youtube channel it was kind of just on a whim like someone asked me to oh god are people from blair here oh god if so why it was kind of just on a whim like i'm pretty sure someone i think niece che asked me to like do a screencast of like some div 3 like around 661 and then other other people from blair i hope not around 661 and like i just did and then i realized i liked it and then i just kept doing it that was basically it there wasn't like some elaborate thing or anything yeah what's up peter i think a graduate but still what is my secret that's a good question i don't know like i honestly wouldn't be able to tell you it's just how you practice and whether you do it right i did not have a strong math background no i did practice a lot at least in the past i did practice a lot yeah i do have math phobia so i don't like this problem but okay okay okay so we say we have specifically x out of order this exact number so let's say x equals one and then um so like but say for example let's say this three is not equal to three so let's say it's equal to seven or something then the problem is if we have this seven here then this has to not be a seven but we can't make it not seven because if we did then we would have two elements that aren't the same so for x equals one there's nothing we can do the answer is zero for x equals two we can do something like this say this is no longer a three then it's a seven and then this will become a three and if it were anything else then we would again have the problem where we have too many elements to change so therefore this has to be a three which means um how many more school years do you have this is my last one so i only have one more shot for ioi so x equals two would mean that you you're interested in the number of ways to pick two positions to put them out of order which is to say you have this number and choose two x equals three then you have three positions all of them have to be together here's why because think about this we'll do the same thing and then what do i make this if i make this a three then we have five positions now but we only have one number that we can make wrong anymore so if we do something like this where we make this a five we can't do this because we've already used all the three numbers no there there's a there's there's like a explanation for being stuck in orange i will look after i solve this problem i'll talk about why why orange seems more like a trap than it actually is so basically the idea is if we make this anything other if we make this equal to this then we end up in the same situation as x equals one so this can't be a three it has to be something different which means this will be something like five and then if we make this something else then we have too many things so this has to be a three and therefore we have a cycle of length three so we're interested in the number of ways to pick three elements to do some stuff okay iq or intelligence that is a question i think it does honestly because cp is padding recognition if you're inherently better at recognizing patterns then you'll just be better at cp like that is that is kind of fact so there is some sort of there is some sort of relevance to like um there is some sort of relevance to how good you are at like pattern recognition and stuff but it's not necessary it'll mean you'll get better faster but it's not necessary to get good because with enough experience if you just like know everything you'll just know everything and then you'll be able to do everything so the more knowledge you have you'll just be better and even though iq plays some sort of a role it's not like a limiting factor it's not like if your iq is x then your maximum possible rating is y or something it's not like that everywhere yeah i agree anyway for x equals three you have three we have um three possibilities x equals four the final one by the way demoralizer i could ask you the same question what um what motivated you to inspire or what inspired you to start your channel are you trying to demoralize people all around the world okay so over here basically there are two possibilities either you can have this cycle b of length four for example like this can point to five this can point to six this can point to seven this can point to three in which case we have n choose four ways that's not a shot i'm just playing with your name i do think your channel is really good because there aren't many like language specialized channels from what i know maybe there's a coder and stuff but other than that i don't know um and then otherwise we could have two cycles so for example we have a cycle like this and then we have n choose ways to do that and choose two ways to do that but now we have n minus two elements and we wanna pick another cycle of two elements so it's just m minus two choose two so the possibilities here are n choose two times n minus two choose two okay this is basically the answer we just like sum of all of these right so how do we um compute and choose k we use the formula and choose k is equal to n factorial over n k factorial times m minus k factorial what is happening one year is a long time you could um learn a lot in one year for example maybe i'll know fft in a year probably not but i might who knows anyway we define this function factorial n to be defined as n times factorial of m minus one and this this would be how you could do um and choose kate but like don't do that because like just don't um because this is like too big you're gonna overflow if you compute factorials and i guess you could hear i guess you could actually think modulo look i think the way it works is because n choose k is always an integer if you computed modulus something then even though you did it the modulo it will still be an integer and therefore if you use a modulo it's going to be it's going to work out but there's like just a better way to do this like n choose k is equal to n times m minus 1 times m minus 2 times m minus 3. or m is k um dot dot dot and this is over one times two times three times dot dot dot times k and that's like the formula you can use because then it won't overflow okay um so oh yeah i guess true because the numbers are big enough for that to be a problem all right but what does this have to do with dp i guess this is i guess this is just the thing i think this is the formula effect number of derangements or something so you can use some sort of dp approach to derive these formulas instead of um like thinking about them i guess and this would be the derangements recurrence or something i don't know is that how that works i guess it would be but that's basically the idea so something like this first n choose k is defined to be this numerator and now seeing the end decay if k is less greater than equal to two yeah the binomial coefficients you can do with dp um that's plus equals nck and two it should be a plus that took way too long jesus actually mostly was answering questions so i guess it was fine and we get zero oh wait uh one because the identity permutation itself is a permutation 12. fun okay why what is what four times three should be greater than i guess it would be greater than yeah okay 21 oh come on oh it's not even that because you can also pick the elements in whatever order you want oh my god i don't want to rewrite this formula but basically the way to fix this is just to like get rid of this part like it's just this i'm pretty sure or not or not okay wait what i'm very confused now have i done this wrong somehow yeah and i'm over counting somehow is the thing like i'm already over counting so i don't exactly know what's causing that yeah i guess that's true it's not exactly equal to that guys this is why i have math phobia this is justification for not liking math you wait okay okay i'm gonna re-explain this after because i'm kind of confused myself i think this whole thing is wrong is indeed a possibility okay so this can go both ways so it actually needs to be two times this and then this formula is even more complicated no yeah i see what you mean how would you even do arrangements there's some dp for durian tunes right the arrangements of four elements are 15. okay i'm gonna trust that wait what let me just look this up yeah i'm still struggling it's more accurate oh you can use pie okay oh my god there are nine derangements okay i'm gonna trust you guys i want to go back to like the standard things that are chill and just like normal dp and not bashing out math what difficulty is this all right okay does it work all right fine so here let me uh let me explain how the hell this happened yeah wikipedia has a table all right so say you have um a permutation i guess there's a less complicated way to say this say you want one element to be out of order like you can't do that because like one element just can't be out of order but say you want two elements to be out of order then you can do something like this where it's equivalent to the number of ways to pick two elements and then the number of ways for them to be out of order yeah sure i'll try and derive it so the first thing is and choose to but then you need to know the number of ways for it to be out of order it's not wrong answer so unchoose two times the question mark and for x equals three and four it's the same thing i guess you would want to pick three elements and four elements but how would you do that because now you need to find the number of ways to make three or four elements out of order so let's say you do something like this you have a permutation of 1 2 3 and 4 for example let's define some function d of n that represents the number of permutations where every element is not equal to its index you can do this in many ways i suppose you can do it with for example like inclusion exclusion principle where you say that like all four elements are out of order and like are at least four out of order at least three at least two i don't know but here's the idea i guess for this element um for this element it has to be something not equal to itself let's say for example it's two and there are three possibilities for that how would this work now so i guess this could be a cycle oh this is painful so this could either be one and then this would close off the cycle and there's one way to do that and then you would have d of n minus two or it could be not one and then you'd have two ways to do that for example would be three and then you would have more things is there a current so event i guess this would that place being not one means you can consider one is two that place okay well this is well researched anyway but that place being not one means you can consider one is two and use the arrangements of minus one for the rest of the array what consider one as two confused now we're getting into generating functions okay all right whatever i don't want to do this anymore there's some there's some way to figure out the number of arrangements it's like some formula something like this okay sure how does this work minus one makes sense you put put that element down okay i kind of just hard coded the formula anyway but the idea for this is that there's some way to count the number of derangements and that is exactly what you want and it's based on dp or something like recursion yeah i know you put you have minus one choice for the first formula and then you like do some stuff and then once you do this it's like then this would be the answer here would be d of 3 and d of 4 because it's the number of ways to have four elements be out of order and the number of ways to pick those elements yeah if it goes into one c of n minus 2 otherwise oh i get it yeah okay sure that's like too smart for me i i unders i understand but i don't want to explain it because it's not that relevant actually whatever i guess i can here's the idea that um gabe at all are saying to count the number of derangements that is the number of permutations where this is where every element is not equal to its own index first of all you have to put this like the element you put here has to be different from them from the original one so this would be for example you have m minus one ways to put down the first element and then wherever that element is either this is the same as this one which is like for example this and then in that case then you have just n minus two elements remaining so you have d of n minus two so one possibility is d of m minus two times n minus one and the other possibility is you have it goes to somewhere else because this has to explicitly not be one which means in the context of this you can kind of replace this with one because this has to not be itself and then you're looking for the derangements of that that's what people are saying i suppose so then in a similar manner you have d of n minus one times n minus one and then you sum those together and it works out okay yeah you people are too smart for me let's be done with this and do more chill things okay we are on the g you the on-board computer on polycop's car measures that the car speed at the beginning of some section equals v1 meters per second and at the end it is v2 meters per second we know that the section of the route took exactly 2 seconds to pass assuming that at each of the seconds the speed is constant and between seconds the speed can change by most d meters weird facebook notifications per second absolute value find the maximum possible length of the path section in meters interesting okay so this kind of screams dp um and the idea would be that here's the statement in short essentially you have some starting some starting speed for example five and then you have some ending speed for example six and you have like a lot of moments in time where things just happen this is way too many you know a lot of moments in time where things kind of happen there's a lot of research that goes into um the arrangements i suppose yeah anyway i'm not gonna bother with that anymore now my math teacher does that it's kind of like it's kind of funny he just like wildly varies his voice at times that's just what i did too so in one second the speed there's some value d and in one second the speed can go like in any range from five plus d to five minus d and that's the idea so now what do we do essentially we want to figure out the longest the maximum possible sum of numbers essentially i think did we count the last one yeah i guess we would it's the maximum possible sum of numbers so um let's do something like this say we're at some value um we're approaching this like a dp problem remember so what we want to do is we want to figure out some state that fully represents the problem so say we're here which means we've already solved for the prefix of the first i times so the dp state has to include the position which would be i but at the same time what else would happen well it would be the case that the time like the speed that you can have here is solely dependent on the previous speed because the speed you can have here like all that matters is um is there enough time to brute force us think of it one second no it's not brute force i mean it's like stuff so the speed this would be would be um solely dependent on this so in reality we just care about the position and whatever the previous element is because when we're figuring out what matters for this state we don't care about this all we care about is this one so let's store the position and the previous value and that's enough because with that we can fully and uniquely determine what we have to do in this current state do you enjoy it when i suffer on problems because that was the case last time i do tend to do that a lot so a dp of i and the previous element would be like what's happening here um my train of thought is like it's not only off the rails it's like flying at this point so i don't even know what i'm doing right so um basically what happens to dpi previous let's do the push dp again because i like i like doing that i do love when i don't struggle but it seems that other people love it when i do struggle so there's some fun in that dpi improve can be pushed to any value where um any new value has my obs disconnected [Music] is the stream still wait is the stream still going what just happened are we good are we not good okay cool wait let me check if it ended on code forces that could have been a glitch okay wait let me check this and my voice is loud yeah it said my obs crashed and then it said it came back up so i don't know what happened there with the qualities down seriously what what does that even mean it still says wait okay what the hell what just happened wait maybe it um it might have reset your quality try try like um like clicking the three dots and setting it to this specifically that might be what's necessary let me set it to lower for my own because i don't want to lag it too much is it fine now okay cool yeah refresh if you have to it may just like be glitched or something yeah that was annoying it just said my obs disconnected and then like for no reason at all and then it came back later so hopefully it's still good i've done streams this long before my computer hasn't had a problem with it i don't know anyway like obviously we can get to any value between these two between and then the value we get is just this value so that's essentially the way this works and we want to find the maximum possible sum so the base case here would literally just be like the first element with the first value that's all we can do and okay how do we do this first of all because we want to maximize the sum there's no point in going below zero since both ending times are above one or at least one so we can assume that all values are greater than or equal to zero actually greater than or equal to one but i'll just do zero because convenience and at the same time t is a hundred and d is less than equal to 10 which means that like the maximum speed we would want to do would be um like around a thousand or so okay stream is probably going to go on for a while you can like leave if you want because the the archive is going to be up anyway i guess it won't be the same fun as the stream itself but and the content itself the content itself will be up later and i also put timestamps and stuff right now we're on problem g i'll put timestamps and stuff so everything will be visible quite easily let's see so this is 10 right so like this value is at most 100 and this value is at most a thousand and this transition effects at most like 21 things it'll it might be longer than 30 minutes i don't know some decent amount of time probably get through at least one more problem i'm definitely not finishing the mashup maybe i'll continue it later in like a separate stream or something that could be a possibility no they're not a they're not sorted by difficulty a to d well a to d are the easiest but then e to o are completely random so for example that's why k has 13 solves okay i'll finish on h facecam facecam at 10 000 subs that's the deal it's not on right better not be on look guys the deal is simple we need 5 600 more it better not be on i have my own stream open if that i would be very concerned if i missed that somehow see i actually have 51 viewers right now because one of them is me on my phone so i can read chat no first of all is 10 000. i don't know what where did egg cake where did 8 000 come from i'm doing a special video 5000 though it's gonna be one of those like click bait things like the uh the journey video it's gonna be great anyway for now let's do this so we can assume this value is at most a thousand and in fact it's at like it's around like at most 600 because you can spend 50 turns going up but then you have to spend 50 turns going back down since the ending value is also around 100 but let's just assume a thousand and then we'll do something like this so start and hello um what is it and okay i'll call it d then we'll do dp and 1000 yeah i did have 4.2k yesterday streams do wonder for this streams do wonders for this channel because like i had 180 viewers at some point and they were all watching me fail to um pin a comment on live stream like look at this what's that the code forces stuff does wonders for viewership like these numbers are crazy okay so um we'll define infinity again no it should be negative because we want to minimize and the base cases dp at zero and start equals zero and then the answer will be dp of n minus 1 and like the the ending value plus the value itself um okay so what do i think of ava's comments like some of them are unnecessarily mean don't get me wrong they are funny some of them but at the same time like i i don't know why anyone would just want to be mean like that it's kind of like a it's like a what is it like a mixed bag or something some of them are great some of them aren't i don't know it's dpi plus one j plus k equals max dpi plus 1 j plus k um dpi j plus the value itself which would be j and this would be negative infinity if we can't reach it vpn and i think that works it does not work i did do the base case wait what yeah and j plus k is also that's not the difference well the state okay the state transition like following the rules of the problem it's kind of simple like you can make this number you can make the next number be anything you want provided that it's within d of the previous one so that's that's how you just derive the transition use what the problem like tells you to do whatever like operation the problem has you have or whatever you need to do for the next element or something just go by the problem and then any transition that works will be defined by the problem and of course um like you want to add j except like this is totally wrong i don't know why and i'm confused now what is happening it should be that this doesn't make sense my okay some sort of index bug that was quick you know i still have the chat open please don't be annoying because i can still do things please make a video on geometric algorithms you know when i when i propose the topic stream idea like this thing i'm doing right now geometry was actually the thing i had in mind but like the reason i'm doing dp is because um like we just go here i made this poll and then i asked everyone what they wanted to happen inside this thing and just like look at this like 800 votes and 66 percent of them were dv there's no way i couldn't do this helps to have mods for stuff like what exactly just happened right now that like things just like people spam or something and it's kind of just weird and it's nice for me to not have to look at chat all the time to just see what's happening tricky and crazy dp optimization stuff like divide and conquer aliens trick maybe i'll have to study for that but i could maybe some sort of like advanced dp section or something that's a possibility why is this wrong this is my concern right now dp zero start is equal to zero for i equals zero is check my code forces inbox what happened there um wait i'll respond to that later i think that's a good idea you could also just ask me here if you want it to not be a secret what really is going on here what's inside this message okay so [Music] um all right let me figure out what's happening right here why why would it be negative infinity when it's like not start exists right like we're reading the input this context is that i'm basically doing a bunch of a bunch of problems and they're all dynamic programming and so right now i'm trying to figure out why this program is wrong because it doesn't make sense but the rest of the video is all about dynamic programming that's the idea i'm picking a specific topic and like going ham on it okay time to print everything maniacally let's have this go up to um doesn't matter um how how did that make it segment what is this do we only go here what do you what does it want it shouldn't be a problem what wait if i no this is fine the fact that it's zero is fine because i'm like i'm doing it weirdly where i count the start here instead of here i don't think that parts the problem the problem is that wait okay okay wait if i make this equal then the problem is that it's accessing us out of bounds and somehow that changes the original values of the array bruh segments are weird like if i make it so it changes less values it makes it correct if i make it if i make it do strictly less work it makes it correct even though i'm doing maximum here that's so weird other videos for hard dp probably in the future yeah see this one is just the trial one trial run i just wanted to see how this would go and seemingly it's going pretty well okay i guess this works i guess i guess the segfault just made it like access the memory that already existed or something i don't even know anyway don't segfault i guess that's the lesson um if you want to see explanation of g you can um rewind the video does it let you actually how far does it let you rewind on a stream let's start about 25 minutes back or somewhat so you can rewind 25 minutes and um i think i do explain the statement i think okay i'll do h as the last one possibly in another stream i'll continue this matchup okay but this will be the last problem i do kind of getting tired right now so we'll leave it as this you one second ah what is going on in this problem admittedly i am losing my focus right now but i mean it kind of comes from experience like usico is four hours used to go this four hours so i have to be mentally prepared to be able to do that and like go for his contests are two hours so going until three hours isn't that bad of a stretch i've done five hour experience before and those were terrible but this is relatively fun you say k um we'll see we'll see is the middle of 2018 false and maria stepanovna who lives outside i can't say this he lives outside of town he wants to rent three displays to highlight an important problem there are n displays placed around a road and the eighth of them can display a text with font size si only um she wants to rent three displays with indices i which is less than j it's less than k such that the font size increases if you move along the road in a particular direction interesting okay [Music] um so the idea is as follows let's see what this isn't so hard to solve this isn't as hard to solve as to find a good way to explain this so let's figure this out if you have a link and a message i think youtube like automatically removes it or something i don't i thought i had that setting to not happen but apparently it does anyway so i don't know okay so this is problem h and the idea with problem h is you have two arrays um one array is an array of values font sizes okay and the other array is an array of 30 20. 10 40. basically you want to pick an increasing subsequence of size 3 such that the the sum of costs of the elements in the subsequence is minimum right now i'm doing problem h so you want to do this so you want to pick this pick three elements so that the cost of the three elements is at like minimize right so the idea here is that if you're at some element so again we asked the question if you're at some element and you want it and you want to put this element in a sequence say like what matters about it so there are two possibilities this element is the beginning of a sequence in which case this is element one or there's some other sequence that this extends um so therefore would have to extend some sequence before it also the basic idea here is that brute force isn't going to work because n cubed doesn't pass but that's irrelevant because you could either you could either begin the sequence here or extend a sequence from a previous one so to extend the sequence this previous one has to have been the last element that was placed in the sequence so why don't we do it like this let dp of i where i is the position and let dp of i be the number of things where this is the last element or i is the last element in the sequence they're not necessarily the last element but the last element that's been placed so far and then we can say that but we also care about the fact that the sequence is of length at most three so let's do something like so where we also include the number of elements that have been in the sequence so far len for example so actually it wouldn't be that i is the last element it's that i is at position len in the sequence then this will be the minimum cost to make this happen right okay now how this would work is again the transition is either you i'm going to do pull dp here because it i don't know why not the transition is either you begin sequence then this would be dp of i one because it's the first element and then it's just the cost of that element or let's say ci or extend then it's dp of i k is equal to some previous value j in the previous position plus ci and essentially this value j must be before i so it's under condition that j is less than i but like that's it that's it because that's just the recurrence either you begin the sequence or you extend one and if you extend one then it depends on some previous dp value so let's do that um and this would be the cost then what would this be dp of n and three or n plus one um for l j equals one two so then simply dpi zero is defined to be where it's the zeroth position so it's just the cost um k equals zero k is less than i k plus plus so then dpi j equals infinity let's just initialize it to that and then it must extend some other sequence so it would be dp of jk minus 1 dpi j equals min dpij dpi dp k j minus 1 plus c i and then ants equals min ants dpi 2 because we can have it so because this is the sequence where the length the the thing ends at i we have to consider all possible endpoints so the answer would be the minimum over all dpi and 2. if no such sequence exists then we'll print negative 1 which means the answer would still be infinity and we get 60 which is somehow wrong because i don't actually check all right if a k is less than aj strictly less that's the condition then we get 80. how does that happen strictly less why is it not behaving like strictly less y equals zero eyes uh this should be i not check whoops speaks 33 uh looks right i think we use i here i j k i i j yeah i believe in it i believe it's probably wrong i don't know doubt is a thing okay you said you want me to try uh problem k i can do problem k and that can be the last problem and i'll understand here or something because this is probably enough for everything all right so okay this is flavor text i'm gonna ignore it because i'm not ready to do anything sequence of l integers where it's increasing is yeah okay so k is gonna be the last problem i do and then i'll end the stream here after that we'll leave the harder problems for later although i suppose e was also a relatively hard one although most of these are going to be the worst so the next stream will kind of be more of like an advanced section i suppose that will work that way and then maybe we'll do some custom problems or something which are probably going to be even harder so that's fun all right sequence of l integers is called good if each number divides by the next number um the next number wait wait wait wait okay okay okay each number yeah divides by is is like confusing but each number divides the next number given n and k find the number of good sequences of length okay okay sure so once again we figure out the way to derive the state what are we going to build the dp on [Music] um first we have to include the position as always and then so we're putting some number down for example we have like 2 2 6. yeah this is the last problem it's going to be over after this and we want to put some number x this is a six by the way not some other thing then all we care about is the fact that x divides 6 or 6 divides x which means x is divisible by 6. and what this means is essentially the only thing we care about once again is the previous element what was the last problem we did wait was that the time one no is that okay so basically the only thing we care about is the last element so let's make this the last element and then this will go out to dp of i plus one and then x where where um or x is divisible by last or last divides x um so like nice um what would happen here let's just remove my message okay interesting i guess youtube is doing stuff to my own chat um but basically it just says that we want to push this value out to all multiples so like what's the deal isn't this like a high complexity um it would be but the trick here is that it turns out to not be because how many multiples do we have of i of 1 we have n of two we have a number on the order of n minus two on three we have a number on the order of n minus three and in general we have a number of on the order of n over i and the total complexity for a single value of that is this we sum from i equals 1 to n of n over i this is the harmonic series it's like probably o of n log n i'm not going to describe it here but actually i did write a blog on this let's just find that right now because why not um and then i'll link that and we'll just leave it as is but essentially this sum is going to be of n log n so the total thing is going to be o of um what would it be k good sequences of length k so k times n which is the maximum value and log n and that's basically it so let's just do that and finish this off there's some formula or something but who knows i don't so this goes up to k this goes up to n so dp m plus one k plus one and we say it like we have one way to make zero and zero mems that will just fill it with a value but be careful with memph set you should probably only use it for zero and negative one so i heard because of the way it works like it's not what you expect um and the way this works is you just kind of like push this out how would this be a base case section maybe it'll be something like this we instead say this starts at one and then we'll put a virtual one at the beginning of a sequence meaning that like all of these values are going to be at most n but they also divide one so that kind of works j equals zero j is less than but it should be k and this should actually be swapped v equals j b is less than or equal to n b plus equals j this is the multiple of j um we do mod it's the first time we're actually doing mod nice dpi j equals no i plus one the next value at v is that we have to do the mod mod and stuff yeah but memphis said is weird be like as you said it does by character which means if you try and set it to like one it's not gonna be one like it's gonna set every eight bits to um that which means in a 34-bit in a 32-bit integer you're gonna get something like that which is clearly not one but with negative well with zero it's just setting it all to zeros and with negative one it's represented like this which is universally negative one so it only works as you expect for those as far as i know but i'm not an expert on mem set you can probably read documentation if you want anyway um and the answer is the sum of all possible like previous values because it doesn't matter what it is ants equals ants plus dpki all right can you run the pro what i read it nice five three nine two we do mod everything's good yeah this lot this stream will um be archived on my youtube after i think youtube may take a while to process it but it'll be up eventually okay and that's basically the idea we do first the position and then the element and then we push it out to all multiples and it just works because um of the way the harmonic series works all right well that's all i have [Music] um okay i think in terms of the stream that's it uh colin galen signing out or signing off uh yeah or kaelin galland whatever you want to call me all right this is fun i guess we can continue this later maybe like more of the mashup or um more of the anything or the implications of this message which you will all find out later okay uh yeah all right goodbye

Channel: Colin Galen

Views: 544,153

Keywords: competitive programming, dynamic programming, learn dynamic programming, dp, learn dp, problemsolving, dp problems, dp problemsolving, intro to dp, dp tutorial, dynamic programming tutorial, intro to dynamic programming, codeforces

Id: zDEQaDl3cso

Length: 230min 42sec (13842 seconds)

Published: Mon Nov 09 2020