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

Hello guys, I hope you can hear me. I also hope this lawn mowing going on outside right now doesn't hurt too much because I know it's very loud. Could you tell me what the audio is like and if this is very annoying? the background i hope it's okay everything should be okay so let's get started hey crystal violet what's up? This is a tradition. Okay, um, okay, let me wait, you can't hear anything, um, that's not good, maybe it's your volume because it seems. like obs is at least pick up my stuff oh wait let me show this to my discord because it's always okay okay okay okay thanks let me send this first normally do this and you know if you want to see this. discord, you can always go straight to the description, but that should work fine, so now the plan is to just do what I was saying.

I'm going to do this. I have this combination of problems that I created. The first four are kind of handpicked and the last 11 are harder and also random difficulty so it should be interesting to see how it goes but wait a second let me also open my chat somewhere else so I can read it and do things at the same time because you know it's a smart thing to set up beforehand, but it's not a big deal, so I'm going to do a thumbnail first because I'm so prepared. for this, setting up the

stream

as the

stream

continues is not suspicious at all, um, it's here, I'll just add this, you know how it goes, because this old thumbnail is the same, um, yeah, it should have some things messed up. and um, yeah, okay, ideally no spoilers, that's not ideal, one second, setting up the stream while it's going, okay, perfect, so let's start with a brief idea of ​​what

dynamic

programming

really is for people that you are not familiar with and at the same time this can serve as a review so I am going to go over a problem that basically everyone uses it but the reason why everyone uses it because it is a really simple and nice introductory problem so do you need know basic dp?

I mean, it helps to know what the concept is, but you don't necessarily need to be able to apply it yet, I guess so, no spoilers, okay, so I'll go with Fibonacci because everyone knows it, so the basic idea is you. we have the sequence, let's call it f of n and it has a formula that is essentially um, it's a piecewise function, which means that for certain values ​​it behaves one way and for other values ​​it behaves another way, so please, Show him how you used to go mow the lawn. maybe later I'll accept custom requests after we're done with 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 cutting fog no no no no no that no that I can't do that okay now this is the problem so if we were to write some program like just use this definition like for example This is what the code would look like, it would just be this and we just write the code that uses the Fibonacci definition.

Now we think about what happens with this code, so we start by saying that we call f of 5. This is also kind of a well-known diagram, let's say we call it f. I'm right now, I'm just briefly going over what

dynamic

programming

is like, why we're doing this, what it's useful for, why it's so necessary and then after that, let's get into the problems, so f of 5, well, depends on f minus 1 which means it depends on f 4. So this will call f of 4, actually I'm going to do f of 3 first but since it also depends on f minus 2. so it will call f of 3 and it will also call f 4. okay, similarly we can, um, we can move on, oh, I didn't do these problems, I just put them together we can continue expanding this tree now f of 1 is just f 1 is as we know it, is as we know it , so this won't generate any more recursive calls, but it will still go down to f 0 and f one. now we do the same thing here we go to f four this will be called f of two and f of three and then we can expand all this in a tedious, annoying and useless way because that's what happens, look how big this tree is. is for f of five, like we need, we want to know six values, but look at how much work we're doing to do this correctly, some of this just doesn't make sense and in fact, look at this entire subtree of calling f of three and this is exactly the same thing, so why are we doing it again?

We just did this here, why are we doing it again here? And if we expand to higher values, we will like to repeat more and more. Why do we do it again? So the goal of dynamic programming is so we don't do it again. We calculate 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 all this out.

We're not redoing this here because we've already done it, that's what dynamic programming does. Basically, we store responses that we've already calculated and use those stored responses to avoid wasting time redoing a bunch of things, so in terms of implementation, how would this work? Well, let's say you just had a large variety, let's call it cache, for example, yes, memorization is a form of dp. I'm also going to go over the other way, like this is called recursive dp because it's one thing, let's say we just had a cache that was sized to store all the numbers. from zero to n so we call f of um five and then we do the same thing, it's based 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 so we continue, this goes to f of 0 and to the right f of 0 and f of 1, of which we already know the answer and then once we do this once we do this now we get the answer for f of 2. Okay, this will be an introductory dp. I'm not really going to go over advanced concepts here, it's probably not in this sequence at all because most of these problems are It's not designed to be the crazy, the crazy, I'm not making money, I don't even have monetization, I'm just doing this right , okay, now f of two we just learned that we use 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 are oh yeah yeah cache okay sure sure scic but we've cached these three values ​​and now we know the answer for f of three because it depends on these two and we know them both, so now we have cached f of three and the comma before. space, okay, whatever and then now we have to calculate f of 4. yeah, f of 1 um I'm not sure, so now we call f 2. now normally f of 2 I would also call f of 0 and f of 1. but first Before doing this, we check that f of 2 is in the cache and sure enough it is.

Instead of recalculating f of 2, we simply use that answer we already know and hack it so that f of 2 is done in a single operation instead of n3 and then do the same for f of 3. f 3 is already in the cache, so we use that response and slice it and that's it, what it means is that each value is calculated exactly once, so there is nothing like it. big explosion of this tree, everything is done once that is the idea and this is called memorization. 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 four. five, so we finished, this idea is called memorization, where we memorize like we memorize but without the r, for some reason they decided that this name was: we memorize the answers that we came up with before and now we know them, so we know them.

We don't waste time redoing it, so instead of this exponential complexity that we would have originally had like 2 to the power of n, we calculate everything once and like everything, it's only based on two values, so it just becomes o from n in terms of complexity, so um in terms of code, this is actually a very simple cache, let's say we're calculating f of 20. Okay, and then we use a negative one because no Fibonacci number can be negative. We use negative one to represent a number that doesn't exist yet, you can also do 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 a reference, but let's see how we optimize it this way if we already know This answer. is not equal to negative one instead of doing the recursive formulation just do this cashback event.

I'll do the subscriber count when we start um, um, like the actual problems, okay, now we know the answer is going to be f of n. minus 1 plus f of n minus 2. So why don't we cache that from time to time? We return that now this is going to be much faster because again it uses this idea of ​​storing answers that we already know, so this is memorization and the other way around. doing it is more popular or more like it is more of what you would call dynamic programming yeah everything will be available to watch again so I will have the file on my youtube so the other way is dynamic programming where instead of like . doing it recursively where we make a cache and store the previous answers, instead we like, we mess more with the idea of ​​using previous answers, let's first calculate f of zero, then make f of one and then make f of two and then we continue in increasing order until we reach f of n, okay?

Why is this useful? Because any value of f of n will only depend on the previous values ​​for f of 3, we only need to know f of 2. and f of 1. so if we have us calculate all the previous values ​​before calculating this one, we will automatically know the answer to um to f of 3. and then when we get to calculating f 4, we already know the answers for f 3 and f of 2. And then we continue to the right, so unlike memorization, which is dp recursive, this is something like iterative dp where you would do it as a loop and therefore you would literally just say um like you. literally you would just do it and then store all these responses in the same type of cache but instead it's an array, yes it's bottom up whereas memorization is top down you start at the top and then you propagate downward. and it calculates the states like this, so you do it in this order and then you say in matrix format f of n is equal to f of n minus 1 plus f of n minus 2.

It's just a matrix, so this is the other way. you would do this, I'll eliminate the memoization and usually with arrays like this you'd just call them dp, I'll actually call them f, I'm assuming n is equal to 20, so we wouldn't actually do the base cases in the loop, like this that first we start with the base cases that we know f of zero oh and the base cases are just values ​​that you know immediately like for example the base cases in these would be zero and one because they don't depend on previous values, how much will the transmission cover?

Yes, he will do it. There's going to be a lot of problems, I guess they're probably going to go on for a while, so we know that f of zero we know that f of one is equal to one and then we just do this, that's it, because that's it, this works because we guarantee that when we're calculating this we already know from previous answers and generally in this kind of dp loop style, what you want to make sure is that, um, yeah, matrix exponentiation, I'm definitely not going to go over that. Right now, but yeah, that's something additional that you can consider, but the idea with this is that you just need to make sure that you increase the font size.

I guess you just need to make sure that when you calculate a value you already know the previous one. values, that's all the order has to satisfy, when you calculate a value you need to know the values ​​it depends on, but other than that you can do it however you want. Now this is called pull dp, where this answer is pulled from the previous one. answers, there is one more way you can do this and this is actually the way I prefer, which is more, it's called push dp and the way push dp works is that f of 2 is based on f of 1 and f of 0. but instead, you can 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 solve, it is based basically in preferences, but the way you would implement this is you still start with the base cases, but now you would go here and say f of i, we'll actually ignore it. zero because it is zero anyway, 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 value of x and then by the Once we get to f of 2 we will have already processed all the things that contribute to it, so in the same way, with the same argument, we know f of 2 by the time welet's get to it so when we get to f of 2 we are allowed to take it out because we already know its answer so this is called push dp hello costa how are you?

Are you tuning in to the subsequent breakup that will happen? I don't have every Monday off, this is a specific one. I'm free on Monday, but usually I'll probably stream on Wednesdays or something because that's also a day I'm open, it depends, that's why you should join Discord because it's always going to be inconsistent the way things are. It always happens that that changes my schedule, so yeah, and the discord that's in the description like it's here, just open it right now, it's here, you can get notifications for everything so that when things change you can still find them or you can also go to the community tab on my YouTube anyway in both places I'll be announcing streams and even in this code forces things like now you can see these things. but yeah, there probably won't be any kind of consistency element, sorry anyway, my introduction to dp took about 20 minutes, i don't know, yeah, okay, now we get into the problems, right? all set so they don't surprise you, but sew you up, I guess it's okay, I'm recording this.

YouTube will automatically upload it as a file later, so it will be fine, okay, I already read this, but you have a given integer and find several ways to fill the three times n tiles with the shape described in the image, oh wait , actually, the first time. An old tradition that I always, before starting, add my current subscriber count to my template and I've definitely explained this before, but the ultimate goal with this is to try to get a memory limit exceeded verdict by making it take up so much memory that is blocked. I think it'll take around 9 million to do it, so maybe next week we'll get a good look at it. you have a given integer n find the number of ways to fill the three times n tiles with the shape described in the image below when filling no empty spaces are allowed the shapes cannot overlap well, so let's think about what we can do with this , we have this grid, let's think about it, wait, figure out some way to draw this.

I'll modify it when I get over um, maybe I actually don't know what I'll do, hopefully, when I get to the code. The forces will have upgraded their systems and it will be 512 megabytes or something so it will never be a problem as I'm sure with the prowess of computing power, like the standard memory limits are higher or something and then the restrictions too They will have to be higher because the computers are going to be stronger. I guess I'm not really sure how far we can go, but it should be pretty good, at least it's okay, so we have to fill all the tiles with the shape ah this is barely visible, we have to fill all the tiles with the shape , um, let's do it like this, which means that no matter what we do, we have to put something in the top left right corner so that there is Okay, so there are three different ways to put something in the top left corner.

We can do it like this. This is one way to do it like that. Or we can do it like this. Let's look at all these cases, what happens with this. problem, okay, so look at this like this is a problem because when we leave this, what are we going to do with this cell? There is no way we can put anything to fill this cell. Wait, it's like there's no way we can put it in. something to fill the cell because all of these are blocked by this, so automatically we can't do this, we are blocked from putting this L shape, so we have two other ones that we can do, we can do this and So what happens here now ?

Look at this cell. There is only one way to fill this cell and it has to be something like this. If we put this one, we automatically have two. How is? We automatically

complete

two of the rows, so this is one way to do it and the other possible way is this, but again look at this cell, look at the cells that are locked when you do this, how does leaving this affect the state? It is more difficult to leave other things and the only way to fill the cell is to do this again, when we place something we cover the first two rows, so there are two ways to do it, we can do it like this or We can do it like this, blue with blue and either way fills the first two rows, so the first thing is that if we have an odd number of rows, then there is no answer and if not, okay, then the answer is the answer that you can think of. mathematically, but this is a dp flow, so I'm going to solve this with dynamic programming, although it's unintuitive, let f n be the answer for a grid of n rows, yes, it's just two to the power of n over two, okay, but I'm going to do it with dynamic programming, so let f of n actually okay, okay, let me, I said that, I told him to the end of his two, okay, first let me say, okay, so everything I've done is Fibonacci, right?

So it's like applying this kind of concept to other things. There is a kind of strategy you can do to approach a dynamic programming problem. There are a few things you need to know in order to make it work. you know, you need to know the state, the state is what information you carry, like what information are you storing answers, for example, in Fibonacci, the state is just n, that is, we are storing the answer of what the hell just happened in chat, uh , okay, I'm going to trust that that silence was justified, so basically the way it works is that we store the answer for a single number and that number is the only information we need; however, we could have other states like we could have. states that are based on two numbers, for example in a grid, a possible state could be the row and column of a cell, so this is not possible.

By the way, I didn't see the messages, all I saw was that they were deleted. So I'm not exactly sure what happened, but this is how it works: it will be two numbers and we can actually have a state that is whatever we want, it can be like 12 numbers, if we want, we can. I have solved the problem before which was six dimensional dynamic programming as it is based on six different numbers and this is stupid but it is possible that the state is the information we need to maintain and with this with the state we should be able to determine in a way only the answer, so I'll talk about what that means later and what kind of states are not enough information because some, like the state, have to represent the whole problem, so there's also something else you need to know. transitions, for example, in Fibonacci, the transition would be f of n equals f of n minus 1 minus now plus f minus 2. in certain problems, this is the first problem of the mashup.

I'm doing the mashup in order, so, uh, I can also find the mashup in the description right now, yeah, I know, no. I'm reading the chat for questions mainly. I just saw something strange happen and I was confused. f of n is equal to f of m minus one plus f of n minus two, so this defines a way to find the answer for a given value based only on previous values. This is a recurrence and um advantages for spamming kailangan igm chad orr will mean ban, I think it's the best, um, I think it's the best reward for doing that, yes, I can fix the current problem, although you must have access to the mashup, so just click on that link f of n is equal to f of negative 1 plus f of negative 2.

So the way this works, this simply defines a way to find the answer for this based on just the values previous values ​​and this is what dynamic programming needs because all we know are these previous values ​​that we have calculated correctly, so there's 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 is equal to zero and f of one is equal to one in most cases this is the only way to make this happen as we need base cases because otherwise There is no end to the things we are calculating, if we didn't have them, this definition of f of n would go into negative numbers and go down to negative infinity because we never stop, we just keep relying on previous values, but these previous values. as if they don't exist, yes, they need base cases.

Someone figure out if Mikey should get a mod. I don't know yet so this is just in the context of Fibonacci um so anything I forgot I guess we'll figure it out later but this is the basic overview if you can find all this information you can make a program with dynamic programming if there is no plausible state that stores enough information to find the answer it's probably not dynamic programming it just depends but you definitely like it obviously you can't apply dynamic programming to everything how can you understand if a problem is dp or not?

It's a tough question, you don't actually understand if it's dp, you're asking like the way to determine if you can use dp is to simply check if you can use dp as in terms of competitive programming, you can try a lot of different solutions and see what will let you give the answer, yes, part of this is experience, part of this is other things, yes, overlapping subproblems is also another way of thinking. but the idea is to just think about dp and then try to get this information and see if you can apply it and if you can't think of any plausible way to apply this 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 mark a problem as dp and then and only then think about it, you can think of every problem and try to solve it as a dynamic programming problem and if it works then it works and if doesn't work, then you can try other strategies. um, dp makes sense until they like it, yes, harder, dp comes with a type of experience that you need to like, there are many tricks you can do with dp and often you just need to do it. find them in trouble to understand, there are too many similar things to go over, but anyway I'm going to explicitly go over this process for this problem, the idea is that for every two rows there are exactly two ways to tile. 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 a way to tile it without rows it just doesn't tile anything so I'm going to use the base case. there's no queue now so base case and yes I'm drawing with a mouse by the way that's why handwriting isn't perfect.

The base case is f of zero is equal to one because zero rows we have exactly one way to do it. just don't do anything, okay the base case is this and now we need it, okay so this is the correct state, the only thing that matters is the number of rows we have, we don't care about the column because we are filling everything. rows at a time, so the column is irrelevant, all we care about are the rows, so the state is f of n, the base cases have a 0 equals 1 and then what happens here says that we have four rows left, well, in a similar movement, we have yes, that is a very good quote those who do not remember the pass are condemned to repeat it in a single movement we can

complete

two rows and we have two different ways of doing it so think about what would this be in terms of f n transition we can complete the row one way and then we add f of n minus 2 because we completed the row this way and now we are interested in the number of answers for two rows because now we don't care about them these rows, we've reduced the problem to having two less rows, so if we fill in one way, we add minus f to the answer, we can also fill it in the other way, which I'll label as brown, we can fill it in like this. which is also plausible and then we complete it another way and then we add another f of negative 2. and the way you solve this is basically think about when you have a problem where you are solving n rows, what can you like, What is the problem asking you to do?

In this case the problem asks you to complete the tiles, so just think of ways you can complete the tiles, that's essentially the way it works. You have two different ways to complete the tiles. both eliminate two rows from the equation, so you're working with a problem with two fewer rows and both ask for the answer of having too few rows, which is f of n minus two, so we get the recurrence of f of n equals one way to do it is to add f minus two and the other way also add f adds f of n minus two, so the recurrence is finally f of n equals two twice f of n minus two, okay, that's It's ugly, where did I do it? learn dp uh, it's um, I think it's a good question, I actually think it was used to go to training, that was my basis for everything, although it took me a long time to understand if you have problems learning dp, that's natural, I It took months. to get um, but at the same time I think one of the problems was that I didn't have enough examples, so okay, I mean this is clearly optimizeable, but the point is that we're doing this withdynamic programming and This is it, this is the recurrence we have, move this, okay, we have our three things, so let's do it, but actually, wait, let's apply the old trick of converting this to iterative dp.

Yes, this is for beginners, let's apply the age. old trick of converting this to interdp where we essentially replace the parentheses with square brackets and now we are working with arrays instead, this is magic right? But now we have a recurrence where we can do an increase. With this, as long as when we calculate f of n we know f of m minus 2, then we can find the answer for f of n, which means it is equivalent to saying that when we calculate f m we want to know all the previous values ​​that we want. do f of n after doing f from 0 to n minus 1, which means let's just calculate f of increasing order, so let's do it like this, yeah, okay, that's true with f of one when you have exactly one row, there is no way to do it because you can't place any tiles for it to work so yes you are right sorry there are two cases base f of zero equals one and at the same time f of one equals zero because there is no way to do it do it if you have one so let's do this now um how does this work c in n um f n plus one we need to know the numbers from zero to n f of zero equals one f of one equals zero for i is two i to n f of i is just two times f of i minus two and then we end up many times onceWe calculate this recurrence and make this all work.

It's just good to see if it works. Hopefully, we get four. We have solved the first problem. Ideally, I won't go so slow for all of these. because it's going to take a long time, but that's the idea, so yes, find the state procedurally, find the information you need, find the base cases and their streams and it's often 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 to repeat infinitely, which means at some point you have to stop, so it's useful to know the recurrence first, so you have to know the values ​​that you need to stop. and in fact, even during this stream, after I discovered recurrence, someone pointed out that I had the base case wrong and needed more information, so it's usually a good idea to find the state first and then find the recurrence that operates on the state and then find the base case that works with it, yeah, also the base cases are the easiest part, um, because it's like thinking about certain values ​​and you can easily calculate certain values.

I'll accept specific requests after this match, okay? this is it, this is all the code, we just 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 do nothing and f of one is zero because with a row there is no way to do anything there is no way to complete these things f of two is equal to two yes, that also works in terms of a more intuitive base case, you can define it like this and then f of one is equal to zero and you don't worry about f of zero as f of zero represents the way to do it with zero rows, but at the same time it's also a convenient implementation to define it as one as if it's more or less the same thing, actually no, I'm not going to talk about it . math, but you can do whatever you want as long as in your implementation you get it right, you can alter things, it's okay to do it as long as it's correct, how can you get to the state?

Well, that's a good question, it's kind of at the same time, figure out what the problem is in posing this problem: given a grid with n rows or a grid three times n specifically with n or n columns, the bad thing, what are the ways to tile it, so these three are? Fixed all three it doesn't really matter for the answer, so the only similar input value is that we have n rows, so to solve a problem in n rows, what can we do right? We can try to reduce the number of rows and we can achieve it. so we have exactly the same problem only with less rows with other things and with other things at the same time, you could just not affect the response or they do and if they affect the response then you need to store them in the state, so as an example, um , yeah, the entry defines the type of state, 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 would be 'If we fix it, we had, for example, um k rows and n columns, then we may need to define the state differently, we may need to define it as f n and k because now the number of columns is important, it just depends on what it depends on the answer and it is It's going to be difficult to figure out the state, that's the hardest part, I think with intuition and trusting

practice

problems and like the problems you

practice

, yeah, fuck, maybe anyway, like with problems of practice and previous problems and things like that. you can get better at identifying what you need to store, it's mostly intuition okay and it's a fun fact that there is a much simpler formula you can do than dynamic programming because people wanted it to just be 2 to the power of n over two because for every two rows you have two The ways to do it and the rows are independent of each other, so it's just two times two times two and more than two times, but there's no reason for that, so that's another way to do it.

I'm just doing it specifically with dynamic programming. Anyway, it's okay. That was the first problem, let's do the next one. It doesn't say that I sold it, I solved it well, okay, now we get into more serious problems. I assume you have a string consisting of n lowercase Latin letters. He decided to write all the substrings. of the string s um is fine, a substring of s is a non-empty string x is equal to s from a to b so it's like a contiguous group of characters um yeah but the keyboard is broken and so it just you can use k different letters in the igm video.

I said don't stop trying things now. I say I have to stop. When did I say that the um keyword is broken? That is, you can use k Latin letters out of 26. Then you are interested in how many substrings you can. I still type using the broken keyboard, okay, it's 20 and it's 285k, it's 26. Yes, the mouse is very noisy, I don't have a better way to draw. I'll eventually get a writing tablet, but not yet, oh trainer mode, okay, that makes sense. I'll stay in coach mode, so it's no big deal oh oh, that's what you meant, yeah, right, well, it's not you who stops, that's the program that stops, that's different, so let's write this formally.

Abacaba, that's how it's done. it works yeah I have a PC2 and no it's just the awesome laptop uh facecam with 10,000 subscribers you guys could take me there you know it could happen it's all up to you now the first step to do this is like the first step. To attack this problem is like what can we type, we can type any character that is valid, that is, we have it on our keyboard, but at the same time all these valid characters are more or less the same, it doesn't matter, yes, I have my bottle of water with me it doesn't matter what the character is, what really matters is whether we can type it or not, so let's rephrase the problem now that we have a bunch of characters and define a character to be one if we can type it using the keyboard and zero if we can't we can like this for this problem where we have abc avicaba and we have a and b as the possible um then all these characters will be ones and the rest will be zeros and now um Asking the number of substrings that we can always write is equivalent to asking the number of substrings where everything is one.

Now there are many ways to do this. You can do it with math. I would prefer not to solve it any other way. This kind of counting problem exists as a universal trick that you should always try, you should try to fix something, I mean, what I'm going to do here is I came up with this kind of intuition, but the way to fix something is to say I'm going to solve for this to be the last character that will be this c, yes, I would use math for this, but it's deep, it's a dp sequence, so I have to do it, so I'm going to do it.

I'm going to say we're going to solve it for the number of k for strings um that end in this character, so the substring at the end of this character, the substring is the end of this character and how does it come? Well, to continue with this, you just have to 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 calculate if I can calculate the answer for all substrings that end in this character like how many substrings we can write that end here, then we can summarize them all and everything will be perfect.

There are many other things that you can fix, for example, you can fix the um. Another thing you can try is possibly the length of the substring you can say we're going to solve for both things for all substrings of length two. I'll take suggestions later, not now, let's say we're going to resolve all substrings of length 2 and then maybe that will work, who knows, uh, it doesn't work here and one of the nice things to fix is ​​the end of the rope, so let's do it now. In fact, I wait before doing it now when when solving a specific end of the chain, what really matters, 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 endpoint and the endpoint is a single. period, oh yeah, the current problem, this is, please remind me to do this, I'm absolutely going to forget it, by the way, this other link is to embed, it's our program, it's our competition, you might want to check it out, It's like he has things like us.

I have had problems with dp in the past so if you want to count more dp you need to check it ok, I can't do this but it was prepared by me and others so I hope it has some level of quality if you like contests. I should check it out, okay, okay, let's get back to it. I can't post things in the chat. Do I have the option to do this? I do not think I can. Oh, we've definitely had dp in the past, at least in 2019. maybe not in 2020. Gotta plug a little, yeah, it's kind of a contractual obligation.

Wait, how can I pin a message? I'll find out later, maybe what I have to do. I'm not sure, oh wait, like a comment or, oh, do it. are you referring to a comment on the video or a live stream chat live stream chat like I'm not sure how to do this this is all I see now I see put user and timeout hide user add modification report and delete what I do? I have to do here like I know I can do it for the comments. I have done it before, but it is not here or not sure what you mean, like these three points, who is in contact?

In fact, I'm not sure I'd try to pin any. random comment not sure how to do this why when I have difficulty going live I have more viewers than actual problems? After writing it, I have this and everything. says for me it's delete now working with live streaming its not dp its mp difficult i have plans to set up a contest on cf actually i did, i did this as a test round and it was just ignored because it was a one off blog and then it didn't a lot of people reviewed it, but I have a round that I wrote, most of the problems are a bit boring, but it exists, if you want to see it, you can find it in the gym.

I'll Google how to pin a comment on a live stream. I can delete all other comments. Sure, okay, I have this open on my phone right now. We're figuring this out. I guess so, I have more viewers than me. How is this like a dream? like 80,000 viewers for a blank screen, how can I pin a comment on my live chat? Oh wait, it takes 100,000 to do it. Okay, okay, look, it says online that you need a certain number of subscribers to do it, I don't know. if it is possible for me because I am not that big in the world of YouTube yet, but maybe later I don't know, I just don't have the option, try to leave the chat, this job, do I have something better here?

I'm not in college, okay, I don't know how to do this. I'm going to get back to the problem. It is a good plan. Yes, I'm in high school right now. I tried to print my own comments, as it were. this just says delete and then that's all I have, I can't do anything with it, okay, I have to explain this again now since we got so far off track, so they give you a string, they give you a certain set of characters you can write you want to know how many substrings exist where you can write all the characters so we define a problem, don't we have enough modifications already?

I think it's fine right now. there's not much to moderate click on manage moderators and then delete niche chat yeah I've wanted to do that for a while actually okay so we define this as one we define it as yes we just found that this It is one yes. and only if we can write it can we use bit masking afterto convert it to zero one, well I wouldn't say it's like I don't think it'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 the number of strings or the number of substrings f of i.

I wanted to pin comments so I could make this exist as it could pin the current issue so it wouldn't be so strange to see, but let's define f of i as the number of substrings ending in i, i.e. no, that's just the number of substrings consisting only of ones ending in i. Why should I make you mod? I need a job and becoming a mod is important on the resume. Well I'm sorry if you don't get hired today so let's say we're solving this character and the first one to find the problem here if you want to read it mod you'll get the message again I thought you were taking the donut anyway so we're here yeah the chat is very distracting I agree so we are here so if this character is one then um.

If this character is a one, then let's say like this, if this character is a zero, then no matter what it is, i is a zero, so there is no way we can have a string that ends in i and has only some because, like us, we no longer do it. t I have a one automatically i is not one so now we assume f then automatically if um let's define this as a matrix a so if a i equals zero f of i equals zero before we continue can we extend this to a subsequence and no is not necessarily contiguous, well if it is not contiguous then it would simply be the number of valid characters and we can have them or not, then it would be like two raised to the number of ones, like minus one, possibly that would be the answer , it wouldn't be necessary to do dp here, but then ai equals zero implies that f of i equals zero, otherwise we assume ai equals one because it's the only other possibility, so what happens?

Well, first we have this, we have the chain. which consists of just ai, so we automatically have at least one, but we also like what about the other substrings? Well, all the other substrings that are going to be attached to this one have to end in the previous character, that's cool, right? Because now we are only interested in what ends in the previous character and well, we are interested in the number of strings that have only one that ends in the previous character so that we can extend them by one and include this character, but for definition is f of i minus 1. is the number of substrings of just ones that end in the previous character, so the recurrence would be f of i is equal to the number of substrings that we can further extend this character into itself because that doesn't would be included above, so plus one and then the answer is over all possible endpoints, how many substrings do we have, which is essentially? saying it's the sum of all the f's of i and the base case is just for a string of length zero for a string of length 0 we don't have ways to do it we don't have substrings because there's no string so we can define is like this actually I'm going to write this in red or something, bitmass bitmasks, yes I have a plan for that, in fact I think the next problem is the bitmask, I like to hand pick that state recurrence base case correct. 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 just going to define a okay, well, it's a um, it's a very strange kind of bit mass. dp dp in trees, I don't think we'll do it, maybe I can do it after streaming, I'll possibly try to find things like that, but let's store instead of storing the number of characters that can be written, we can store an array instead. for each character and check if that character is writable or not, that's true, an array is a degenerate case of a tree I guess, and then we say automatically the default value is zero, so we read a character and now it's in the keyboard. so we define it as typeable and subtracting from just means we normalize it to the numbers 0 25 instead that's what it does, so now what we can do is rephrase it, we can create this array a which is one if a character is typeable and zero if not um if typeable s i minus a a i is equal to another a i is equal to zero and of course you can get rid of the if condition, you like ternary things, it doesn't matter uh, I don't have school today specifically i normally we have schools on Mondays because this was like the end of grading period or something now let's define the function, this is the function dp and the base case is that f of 0 is 0, which we define and then use this is like this, if a i is equals zero, so our current says that f of i is equal to zero, except we have an index of this, so we have to add to i plus one, not specifically i and otherwise f of i plus one equals its current states f of i plus one, then the answer is the sum, so let's do that too and that will be it.

I'm so glad you can't record this on YouTube. I'm so glad you can't make clips on YouTube. because I'm sure many of me will have a hard time pinning a comment, it would be sad. You know, part of the great thing about YouTube is that because I've stripped down the solution so much, there's a good chance I'll like it. just be right on the first try, so sometimes it's an idea to think hard about a solution before going into it blindly. You can use dpa instead of recursion, it doesn't necessarily depend on the idea of ​​dp being to remember previous answers.

If you have previous answers from 10 to 18, such as it depends on an array element or something, then that won't necessarily be possible. Well, it's not necessarily a session because this entire live stream will be available. on my youtube channel after making it, even if you missed some of it, it will still be here. I also intend to resolve these later issues faster. We got really distracted here, but the idea of ​​dp is to remember 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 won't help that's where it applies ok on the next one yeah this is where bitmasks come in .

The bitmask comes into play. The current problem is updated, I'm just going to highlight that it's okay, the Berlin store sells any type of juice, each juice has its price, each juice includes a 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, future. I block 1v1 with a second thread, that's a possibility that depends on things I see as a possibility that could happen in the future. Yes, collaborations are also possible. There are also many other channels that are starting up and doing tutorials.

For example, this guy that the algorithms conquered is one I've seen before, so you can see it. There are others too, but yes, I'm sure collaborations are possible in the future, we'll just have to set things up. backpack dp yes it's a form of dp it's fft dp I don't know fft but probably not I don't think it's right so each juice can contain one, two or all three types, we need to get juices so we can have all three vitamins es greedy dp usually no, sometimes usually no, so what is the minimum total price so you can get all three vitamins right now?

This one is a little more complicated because the state is not that 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 it's tpdp yes no it's not but what is x well what we want to know is what is the cost to get all three vitamins correctly and these vitamins are unrelated to each other so the way it works is how can we do it here in some kind of state, we need to have it so that we have information about the contest is restricted, yes, to open this issue you first need to click on the first link so that you can be invited and then you can open the specific one. problem, I'll put it there, so we need to store whether we have the vitamins or not, this difficulty is 1200.

So in one state, we need to know if we have vitamin a, we have vitamin b and if we have vitamin 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 have it this is a zero if we don't have it or a one if we have it this is a zero if we don't have it We don't have it and one, if we do we do, there are two ways we can represent this, we can do it like this, we can do it with three variables and we say this represents whether we have an a or not, this represents whether we have a b or No, this represents whether we have a c or not and that is a way to do it, but there are also other ways to do it.

Instead of doing that, we can compress these three into a single number because notice this is zero. and one this is also I'm doing problem c this is also zero one and this is also zero one this is binary it's not that cool we're interested in the binary state of do we have air now whether it has a b or not whether it whether we see it or not, but I think just think about computers, like computers do things in binary, we use numbers in binary, so why don't we just make all this a binary number?

Let's have three digits for the first one. digit is a the second digit is b the third digit is c this first digit represents whether we have an a or not the second digit represents whether we have a b or not and this third digit represents whether we have a c or not then a has the value from 2 to two squared which is four b has the value of two to one which is two and c has the value of two to zero which is one we are doing the problem c I'm going to I'm going to how to do this now I'm going to write what's at the top and we will compress this binary sequence into a single number that represents them all 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 a bit mask dp we ask we have a recursive we have a state mask f which basically says what the minimum cost to have it so we have satisfied everything that the mask says that we have for example if the mask is 1 0 1 which is equal to 5 then we have to be satisfied that we have an a and we have a c uh why is it called roll? I don't think you can super chat, I don't have um.

I'm not a member yet and I haven't even applied. I should probably do that at some point, but I don't have any kind of setup for that, so skin represents the lowest cost to satisfy skin that we can also present. another state, this is sort of implementing whatever you want and the mask, which is defined as the lowest cost, the lowest cost to satisfy the mask where you've only used the first n strings, this is generally how you would do dp because you We're going through the strings so you can abstract this part and just get rid of it, it will be implicit, but this is the explicit definition of how to do this, it's the application, it's the lowest cost to satisfy the mask using the first final string oh, where do these numbers come from?

This is how the binary works. The first thing takes one's position. The second thing takes the position of two. The third thing takes the position of four, etc., as if it were just a binary number. That's all. what 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 also represents a kind of set of objects and then the bitwise operations do some interesting things. Go with this, so f of n mask is the lowest cost using the first n strings, okay, how do we do this type of recursion?

This is where I prefer to use push dp, so I'm going to describe how to use push. dp right now yes, three variable truth table, sure, so what does the mask f of i contribute to? So the transition for the mask f of i will consider i plus a string and what we can do is represent these strings as a bitmask as well. we represent the string as a separate bit mask that asks if we have an a in this string, we have a b in this string and if we have a c in this string and we do it the same way this is two to two this is two to one this is two to zero and then we'll call this mask m or something like that 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 that the transition is us Or we don't take the string i anymore one, in which case we still have the mask f of i plus 1 because we've considered the first string i plus 1 and we just didn't use it this time, so either it's okay or we do it.

Use it, in which case we have to consider what happens, so this is f of i plus one because now we consider the strings i plus one, but what happens here, well, this is where the truth table comes into play, so which can order to discard the way to make this transition in this way, we can say that we had it before, we may have had it before, in which case we don't care if thewe have it here or we have it here, in which case we don't care if we had it before, so there are four cases, or we had it in both, we had it before, but not here, we had it here, but not before, or we haven't done in neither, and well, this is just asking if you have it in at least one of them, we have it no matter what, so this is bit by bit or are you going to bit by bit or the masks together because if you have the bit in at least one of them, then you will have it later. so it's a logical mask or m and the cost of this is the cost of taking string i plus 1. then you would have to consider f of i mask plus the cost of that, the base case is we simply have zero strings and obviously we can't have anything satisfied , so it's zero because we don't have any cost either, so now let's make this binary number just the number between zero and seven so that we can represent it in an array of size eight, first we need the 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 if we can't get to a state, then we want to make it so that we're never incentivized. To use that state, one way to do it is to simply initialize everything to infinity because that is the highest possible cost we can have and therefore we will never want to use it, so let's define infinity as a huge number like 10 to the power 17, that we will never reach cost because costs are only 10 to the fifth power, so f of i and j is simply infinite, this also gives us a convenient way to check if we can't have it at all because if we never reach the state where we never get to any state so we're totally fine so we also define the answer as infinite and then we say cost string s so now yeah if you look at it later and leave a comment I'll try to do that. answer int string mask is equal to zero so for ins um like this is the position in the mask I'm going to continue 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 of 2 to the 2. then the corresponding character is this minus the position, so in the first position it will be a c, the second will be a b, the third would be a, let me check the string and see if we have it then if we have it string mask plus equals one shifted left by pause, which is the same as saying two to position, okay, there is the possibility of live subtitles, you could try that, but I'm not sure if it's possible, wait, what is this?

If your video doesn't require subtitles, it should be automatic. If not, I assume you will have them after waiting. Can you enable them? I guess not, it's a bit annoying, yeah. I guess it's not possible to live, sorry, we'll have to figure that out later, I'm not trying to do that, okay, let me finish this, so for a certain value of i just we like to iterate through all the possible values ​​and masks which is zero to seven and then we find what pushes like so um the first case is we don't take anything and therefore we just do this so f i plus a mask is what same is equal to min f of i plus a mask um f i and the mask, that's the first case and the second case is we do the same thing, but we take it so that f of i plus a bitwise mask with string mask is equal to the minimum bitwise generation mask or string mask plus the cost of taking this string, which is cost and then the answer is any possible form of the answer is the minimum cost after having considered all the strings to have the full mask of a b and c then the answer is um we define it here f of n and 7 because 7 is the number that represents having all the bits enabled if the answer is infinity then we never reach it and therefore we want to print negative 1. and this is how it works this is bitmassdp in a sense which doesn't match the fi mask and it breaks okay uh cool oh because I'm never right we want the base case to set this to zero as we define here fifteen this should be negative one we don't have an answer should be thirteen should be two fifty should be 16.

Okay, by the way, at the time that I have for the broadcast I don't expect to go through all of these that's not the point the point is that like we um the point is that we just don't I know I'm trying to be elaborate here and trying to explain everything and yeah, the point isn't speed, that's what I'm saying, I kind of lost my train of thought a few times, we get the deal, dude, okay, yeah , there is no reason to submit a question six times. I'll try to read the entire chat. and if I don't, you don't have to keep saying it, but practice div two, I'm probably not sure that's the way to go, yeah, don't spam that's annoying, the time I'll last only five minutes. so we can talk more later, so this is just d.

I don't even have to change the link every time, it's just a problem. d um, yeah, let me read the rest of the chat. I may have missed things. Where can I practice number theory? I think you can, that should be a label, go to the problem set and then add a label and then number theory and here you go, you can also choose difficulties if you want, like 2400 to 3500, which I'm not going to do, but you you can do it. whatever you want coforces is pretty good, these are all 1200, um, the first one, the way this distribution works is the first one, one thousand, the next one, three hundred or one thousand two hundred, and then the rest are randomly distributed between one thousand four hundred and two thousand, so some of these are possibly quite difficult you and your friend Mishka attend a calculus lecture afraid to say names lecture there are so many ways to mispronounce something the lecture lasts and minutes he says ai theorems during the eighth minute um it's a really interesting calculation but it's hard to stay awake given the correct t of music behavior, mishka is asleep during the eighth minute of the lecture, so ti will be equal to zero, otherwise it will be equal to one, which disappears, he writes all the theorems he is told, otherwise he writes them down. keep them awake for k minutes straight, you can only use it once you can start using it at any valid minute you want to work.

Make sure your task is to calculate the maximum number of theorems you can write if you use your technique. Only once, so wake him up. Watch the video of your competitive programming journey. I mean, you could go the same route. It is not necessarily necessary. There are many ways to improve, but I'm not sure. I think it's like a general good. The general rule of thumb is to practice whatever you want to be good at, so if you want to score 12,000 in code strengths, you can do a lot of code strengths problems because that will tell you exactly what you need to be able to do to to get it. 12000 code forces rating is ok why this dp is a good question.

Well, you can think of it as this juggling practice later. I will do it today. I said. I will do it today. I will do it today. Wait. I hope that's 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 in some sense of the word it's not quite right actually no it's dp for sure so this is one one zero one zero zero and the way this works is you want to choose a range and then automatically you will get all the numbers in this range but at the same time you will also get all the numbers in this range where you have a one but not the numbers where you have a zero, um, so let's do it like this, let's say we choose an arbitrary range, so what we're interested in are three things, the sum without modifying the numbers of this, the sum without modifying the numbers. of this and the sum of all the numbers in this, okay, now there's a cool way to do this and a not cool way to do it.

I'm probably finding that it's not great, so here's the idea. The idea actually exists, so. What we're interested in is the normal sum of this, so let's split this into three parts, we want the unaffected sum of this array prefix, we want the unaffected sum of the array suffix, and we want the total sum of this. so in dynamic programming terms it's like it's still building from previous answers, let p of i be the unaffected sum of the prefix, okay, then 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 is everything but the element you just took, which is the same as the previous prefix, so p of i is equal a a of i whatever a of i is, this could be zero if the value is zero or something greater than zero, otherwise plus p of i minus 1.

In a sense this is dynamic programming and we can do exactly the same for the suffix s of i is the unaffected sum of the suffix actually let's say it's the suffix of the last characters i because that's quite convenient actually no it's not, let's say um is the unaffected sum of the suffix from i to n and then we're I'm 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 equals a of i plus s of i plus one well, those are these two parts, what about the middle part is not so fun?

Well the idea is this is a thing, why are you spamming points? This morse code I can't read the morse code. Is there anyone fluent enough in Morse code to understand this or is it just nothing, so that's annoying, but oh yeah, I guess you can mute it? I don't see the point of that mashup being active, yeah, everything like this whole stream, everything is It will be available later, so you can find the problem first, click on this link and then you can click on this one specifically, everything will be on the description, but yeah, everything that combines the video, everything will be after, it's like it's going to be available after, well, this is something interesting called prefix sums.

We are interested in the sum not of the unaffected sum but of the sum of all the elements of the array, so let's do it like this: let the prefix of i be the sum of the first elements of the eye are not the sum no affected, but the sum of the first elements i specifically, then it is the same recurrence as p of i. I will do it with the green prefix. It sounds like my math teacher's i prefix is ​​equal to a i plus the i prefix. minus one and the way this works is what we want to do: we want to use this to get the sum of anything, get the sum of any range, so let's consider some range that we have in the array, but we want to represent it as some sort of this prefix thing, so let's consider all the prefix that ends at the end of this range, okay, but look, look man, we have this similar space here, what we are interested in is this and we have all we know is this, right? so what if Just like we do this, but we remove this space and then we're left with what we care about, so this space in this range l and r this space is the prefix of l minus one elements and then this space is the prefix of r, like this that to get the sum in lr we just take everything and then subtract the stuff we don't want, so it's the prefix of r minus the prefix, I'm capitalizing l so you don't also see a one minus the prefix of minus one and that's how you would get the sum in a specific range.

This is more commonly known as prefix sums, but it's like it's a form of dp, so it still counts, I guess I think that's why I was Labeling that, so now let's do this. We're going to this is going to be tedious and there are simpler ways to do it, but I'm doing it explicitly because it's just nice, so we use ai to represent the first array bi to represent the second array and we can think of it like this, so we do it I will define 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 that p of 0 is equal a a of 0 multiplied by b of 0.

This is convenient because if it is 0 we do not want to count it and if it is 1 we do want to count it. count it, so if we just multiply it, it will work, 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 for the suffix I'm going to enter order, yes, but the general idea here is that once we're here the way this will work is cadenza, not sure how that would be applied, it's like a fixed range subset, we can do the same thing except compute prefix sums, usually .

I have a specific trick where instead of making the array explicitly, I store a variable that represents this and then it's no longer a recurrence, it's like you just keep this variable that represents the suffix as you go. We're not going for eight hours now um r plus is equal to i multiplied by bi and you can do it like this and that makes it so you don't have some kind of edge case or anything like that and we can do the prefix sums, isn't this font size? enough, I can't get much closer, anymorewhich becomes uncomfortable.

This is the quality. You can also improve the video quality, I think, but the way this would work would be: I want to find the best, so let's fix it. the starting point of the interval that we are using um i plus k minus 1 is less than n because that is the end of the interval and now we say we are going to do this throughout this array, we take this interval, this is i the end of this is i plus k minus 1, which means 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 the current is equal to zero if i is greater than zero the curve plus equals 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 simply like this, we consider the prefix of r, if necessary, we subtract the previous one and Now we consider it the answer, all I'm doing is writing.

I guess it works, although this exists, in fact, so we just like to calculate these three things and then combine them. I said this wouldn't be easy and it's no, but it's a way to force it to be dynamic programming, that's what I'm trying to do here, okay let's do it, it looks like this has fewer solutions than normal, so That sounds fun, let's do this. n people on keys in a straight line, each person wants to reach the office that is on the line and for this he needs to reach some point with the key, take the key and then go to the office, what is the shortest time ?

I finished this co-force contest, that's a good question. Yes, you can also make gifts from scratch. That's officially true. I think it was like 40 minutes or something in some division three, I don't remember exactly, so you need something. arrive at the point with a key, take the key and then go to the office to determine the minimum number of people who need it for n keys, okay, so let's think about this, you have a group of people, ideally I will try to go a little further fast. through these you have a group of people, each person is located at some point, let's think about it like this and you have a bunch of keys, the keys will also be somewhere, yes, William Lynn is quite fast, I agree and the way this is going to work, each person goes to each person is going to take a key, oh and there is also some office somewhere, I guess that's how it works and each person is going to take a path that first goes to one key and then it goes from that office key, oh yeah, that div 4, it took me 37 minutes, I guess that would be it, I didn't care though, you read a problem and you don't have an idea, try to get more ideas, like no you would understand an idea instantly, that's normal, usually, difficult problems take a while to even think about something, but then as you think more and more about it, things become clearer, for example, you may find some observations or stuff, it's a possibility, um, yeah, it's very fast, I would agree, it took me a while to kickstart g because I like it, I'm bad, well, the problem c was like a pain, okay, so the basic idea for this problem is and I just came up with this so quickly because I've seen it before, but I like it.

You don't, the trick here is that you don't want the paths to cross, so consider something. I'm going to move this down. Consider something like this. Well, first of all, you will assign each person a key so we can think. of this so where we just draw this task correctly and then this person will go here forexample, what to do if you are stuck in new co-forces, that depends on how effective your practice is, if it doesn't work you probably want to try something else, I guess you want to see what works, what doesn't and I'm not sure that getting better is random, you just have to throw yourself into problems and get better at thinking and the only way to do that is to have the experience.

I don't think I have a greedy solution. there's no guarantee the greeting is going to work, you've known me for about three weeks, there's no way the greedy solution is going to work, wait, I'm going to draw this here, so now let's consider this, these paths crossed. So the idea is that we don't want to cross these because consider this, consider it like this, let me find some way to illustrate this, I'm not sure if you have the best possible solution with greedy, but I don't think it works, that's the thing, so you have a task like this, but like I say, this green task will always be better if you have two paths where this is less than this and this is less than this but this is assigned to something after this, then it is not optimal and this is fine acquaintance.

I mean the way to demonstrate this could be something like this where you could possibly do the case work like you can do this guy. of case work and realize that in all possible cases the green assignment will be better, but this is true, since it is an idea that always goes to seven streams for a single contest, what the heck, basically, will this thing be green? Better let me try to find some non-obtrusive way to test this because it's like you do all the cases where, for example, the blue dots can be between the red ones or they can be on one side or the other.

On the other hand, there are many cases that everyone can solve and everyone will say the same thing like this green path which is a green task where if you don't cross the paths it will be better, but that is the idea that Basically means that the key assignments What you do will be in increasing order, so you have the numbers one, two, three and four and you have five possible spaces. So it will be something like this, for example, this would be the assignment, but you can't cross them so you don't have something like this.

Each similar assignment number will be less than the next. Why do I say this so elaborately? What it means is that you can automatically assume when you have assigned the third person. that you already assigned everything before that third person and we're trying to do dp here correctly, we're trying to get some kind of reasonable state that represents everything we need to know for the problem and I just showed that the only thing we need to know for the problem is the last person we assign so that's fine and also the position we like the position we are in and the last person we assign so if we were to write some dp based on this. would be the dp of the position and the last person, that would be the only information we need to know because with this information we can uniquely determine the answer and the problem we are solving and everything, but you see how this would not work.

Yes we can do them in any order because it is not enough to just say that we scored three at the end because now, what happens if we then score one or two? It says nothing. All we know is that we write down three, but in this problem specifically writing down three implies that we leave everything and it also implies that the next person we are going to leave will be four, so with this information we know everything and that is why dp works here. I'm not exactly sure how to test this kind of lemon-like thing, but this is how it would work and I also notice that the cost of going to the office doesn't like to change when you do this because you're still wearing the same outfit either way. of keys, so the last dp position is the minimum cost to have it, so you are in the position, yes you could use bitmaster if the order wasn't so fixed, that would be an example of bitmass dp, I guess, but yes, you would have two. until the end he says and that's just not going to work um how did you do this?

So this is the minimum cost to be in this position and you've used um first, the like you've already used so many people, so the answer is the maximum. general um is the maximum let me see the way to retrieve the answer is just the general maximum j of our general maximum i I guess dp of i and the number of people you have, which is n because that's how it is It doesn't matter the final position, the only thing that matters is that you used all n people. Okay, how do we calculate this? Well, let's see to press dp or not to press dp, that would be the supposed question, oh yeah, right, sorry, the least.

You're right, you're right, you're right, okay, I would have read the sample and realized that eventually it didn't make sense, but yes, it should be the minimum, so the reason I find push dp so intuitive is because use the problem statement with push dp the transition is, you either assign a person here, in which case you get a new state based on that assignment or not, that's why I think pushdp is so good because you don't have to like reversing the transitions to figuring out how things work jenna how things work in general pressing dp is where you explicitly use this state and push its value to future states like a pause plus a last plus one oh my gosh that ham is working yeah.

Jesus, but that's the idea that you use the state to carry that value into future states. I think that's the easiest way to do this to make the dp pause last. You have two transitions, you either take this one or you don't, if you do. end with the plus one position and now you use the new person or this is the problem e in my mashup which you can find in the description or you don't take it in which case you have a 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 good with push dp. I agree that dpf 0 and 0 will be defined as 0 and everything else will be equal to infinity because, like us, I don't want to accidentally say, for example, that we are at position zero, but we have used a person because that could lead to an answer that is not good, so we want to initialize everything to infinity to make sure that I don't like to accidentally see states that don't exist or something, but here's the idea: we're going to assign things in increasing order so we can do dp.

It's like it's a little bit like the dp of what would it be like? actually no, it doesn't matter, it looks like the longest common subsequence, but it's not right, let's read the llp values, so let's read that into um and then we do that and then we read the first k values ​​and we want to sort. them because otherwise the order we make would not make sense, we want them to be arranged in increasing or non-decreasing order, so we define dp in the following way, we have n plus we have k plus a possible position to be in because zero is like a nonexistent position and the same for this is like a nonexistent number of people and we have n plus one possibilities for the number of people we get, we can be within the range from zero to n, so we do this um dpi j is equal to infinity which works fine um 1 10 to the power of 17 is big enough yeah so now let's review i is equal to 0 is less than or equal to k I didn't even do the training transition but oh yeah yeah we did it we did it .

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 first we don't take the person and then it's just dp. I would welcome you, but I don't. I still know how to pronounce your name so I can't i plus one j equals min dp i plus 1 j dpi j if this is infinity itself then we just ignore it because it's like minimum infinity and infinity and then take person, this is only possible if we are not yet in the last person, then 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 Well, it is like it's just the size of the array what really matters is how you define it and I define it like this, we're in this position and we've used so many people, so we have zero to n. like the chances for people are zero to n, the chances for positions are zero decay, that's how pushing dp works is what I'm doing right now, it's essentially the idea that instead of having dp recurrences, rely on previous states, you use previous states to push them to future states, which is what I'm doing, so this would depend on dpij plus cost, which no, it's not really, I mean, it's pretty much what same, like you can study whatever works for you and almost universally it's going to be fine as there are a very small number of problems where a certain type is necessary generally both push and pull dp will work so this is dpi plus one j plus one dpij plus um the the cost would be, let's see, it would be the cost between um, it would be a j person j minus b j this is the distance between them and then it is the distance between that key location and the position of the um position yeah pushing dp is more of a style choice than a concept like its no different its still the dp dp series below that i can cover maybe i can cover act code and like the dps credited in a different video or something like that, yeah, we can also define it as dp we can also define it as dp.

I'm going to do this in different colors, like for example dp of i j is like the minimum 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 mean I prefer to do push dp because it feels easier, yeah I'm not sure where the timestamp is, it's like near the 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 carrying to theI check well if ak is less than aj strictly minus that's the condition then we get 80.

How does that happen strictly minus why doesn't it behave like strictly minus and it's equal to zero eyes uh this should be i? no check oops talk 33 uh it looks good I think we use i here i j k i i j yes I believe in it I think it's probably wrong I don't know the question is one thing okay you said you wanted me to try it uh problem k I can solve the problem k and that could be the last problem and I'll understand it or something because this is probably enough for everything okay so okay this is a flavor text I'll ignore it because I'm not ready to do anything sequence of l integers where is increase is yes , okay, so k will be the last problem I do and then I'll end the broadcast here, after that we'll leave the more difficult problems for later, although I suppose it was also relatively difficult, although most of these go I guess it will work out that way and then maybe we'll do some custom problems or something that will probably be even harder, so that's fun. the sequence of l integers is called good if each number is divided by the next number um the next number wait wait wait wait okay okay okay each number yes divide by it's like confusing but each number divides the next number given n and k find the number of good length sequences, okay, okay, sure, so once again we figure out how to derive the state in which we are going to build the dp.

First we have to include the position as usual and then we are putting some number, for example. we have like 2 2 6. yes, this is the last problem that will be solved after this and we want to put a number x, by the way, this is a six, not something else, so the only thing we care about is the fact that x divide 6 or 6 divide x, which means that x is divisible by 6. And what this means is essentially the only thing we care about once again is the previous element. The last problem we expected was that the moment one is not well, 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 to dp of i plus one and then to x, where um or x is divisible by the last or the last divides x um, so it's nice, um.

What would happen here? Let's just delete my message, okay, interesting, I guess YouTube is doing things in my own chat, but it's basically just saying that we want to push this value to all multiples, so what's the problem? It's not that high? complexity um, it would be, but the trick here is that it turns out it's not because how many multiples do we have of i of 1? we have n of two we have a number of the order of n minus two over three we have a number of the order of n minus three and in general we have a number of the order of n over i and the total complexity for a single value of that is this, we add of i is equal to 1 an of n over i this is the harmonic series is like probably o of n log n I'm not going to describe it here but I actually wrote a blog about this, let's look that up right now because why not? um and then I'll link it and we'll go. is as it is, but essentially this sum will be n log n, so the total will be or um, what would be k good sequences of length k, so k multiplied by n, which is the maximum value and log n, and that is?

Basically, so let's do that and be done with this, 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 memories that will just fill it with a value, but be careful with the memph set, you should probably only use it for zero and negative one, so I hear the way it works it's not what you expect, um and the way this works is to just pull this out.

What would this be a base case section? Maybe it's something like this. Instead, we say this starts at one and then we'll put a virtual one at the beginning of a sequence. which means all of these values ​​will be at most n but they also divide one so that kind of works j is equal to zero j is less than but it should be k and this should actually be swapped v is equal to 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 good dpi j equals no i plus one the next value in v is we have to do the mod mod and stuff yeah but Memphis said it's weird like you said it does it per character which means if you try to set it to one it won't be one like it's set every eight bits in um which means in 34 bits in 32.-bit integer you'll get something like that, which is clearly not one, but with negative, well, with zero, you just set everything to zeros and with negative one, it's represented like this, which is universally negative, so it just works as you expect.

Those, as far as I know, but I'm not a memory pool

expert

, you can probably read the documentation if you want anyway, um and the answer is the sum of all possible previous values ​​because it doesn't matter what they are, ants is same as ants. also dpki is ok, can you run the pro? What I read right five three nine two we do mod everything is fine yeah this lot this stream will be archived on my youtube after I think youtube may take a while to process it but it will. eventually I'll get up, okay and That's basically the idea: we do the position first and then the element and then we take it to all the multiples and it just works because, the way the harmonic series works, that's all I have, okay I think in terms of streaming that's it uh colin galen log out or log out uh yeah or kaelin galland whatever you want to call me okay this is fun I guess we can continue this later maybe like more of the mashup or um more of anything or the implications of this message that everyone will discover later, okay, yeah, okay, bye