Complete Dynamic Programming Practice - Noob to Expert (Continued) | Topic Stream 2

hey guys uh i realize i'm slightly an idiot because i've been streaming to twitch for the past minute i didn't even realize it wasn't going here um so that's kind of fun so yeah this is a good start um anyway what i was saying to nobody apparently is that i was sad about actually wait is it working on code forces oh it's like glitched yeah okay let me put this back up um it's not finished so i'll do that yeah okay but anyway the way these notifications work is that like you this this plus 149 thing that i've had for like three months is just gone and i'm really sad about that and the way these notifications work is that like it's based on this thing this share it and so if anyone clicks on this not even myself if anyone does it the notification will go away which is annoying like what kind of design would have it so someone else clicking your notification would make it red it doesn't even make sense um anyway the plan today is to finish this i haven't added the hard problems because i probably won't get to them in time so let's see let me link this where do i go i gotta like do some stuff send it out to the discord okay yeah there's also like this top coder thing going on so um oh the share it thing like there was this if you go to any of my previous videos you'll see this message like you have plus 149 wow and then it just went away um i'm not gonna say your name if you put that in the message where no i can't like combine that see crystal violet has a normal message so i'll say their name sure okay what was i what was i saying i'm not actually sure what i was saying yeah there's this like top coat of thing going on and it's like a bunch of things so you could um like that exists too and if you want to see that that's fine because this um stream is going to be up as an archive anyway so you won't really miss anything okay so as it turns out i got one of these problems in a duel and i like solved the accidental even though i haven't solved it on this which is like stupid i didn't realize that but the good news is i didn't actually solve it with dp so i could use the dp approach to um solve it in a different way and therefore it'll be like i haven't solved the problem yet so we'll think of it like that because the way i solved it was something else so i'll force it to be a dp approach and then it'll be a different problem uh yeah okay anyway so in terms of the plan i'm just gonna go through these problems uh wait actually let me check and make sure everything's like set up right um you guys can see i'll get rid of the poll you guys can see the mashup link and the previous stream here in case you missed something no you get ignored because of what was in your message okay so do you guys remember last time the last topic stream where i spent like five minutes trying to pin a message well it turns out i just unlocked that like a week or so after the first topic stream happened so i i was right it wasn't possible to do it yet but now it is possible so um i think i can do it like this current problem i and then i can pin this or something yeah all right you see so now you can see the problems that's like actually happening apparently not on mobile though so have fun with that i don't know this work it should work fine i'll say your name what's up sophie what's up sam how are you doing okay it's time to actually start how far away into the stream where i haven't actually done anything yet so this first problem is called problem i mike and fun mike and some bears are playing a game just for fun all right um in terms of the pin like the pin was like it said i just unlocked it like i opened the streaming window and then like right here or so it's a new feature you can now pin messages so i wasn't able to do it before but now i have it i don't know what made me get it but um it's working now and actually i'm gonna remove that and make it a link so you can open it straight from here uh and i'll pin this one okay does this work i hope so yeah okay yeah they saw me try really hard for the pin all right all right all right mike and some bears are playing a game just for fun mike is the judge all bears except mike are standing in end times m grid there's exactly one bear in each cell uh we denote the bear standing in column j of ron yeah yeah mike's hand are on his ears like it's a it's a grid row i call him j mike's hands are on his ear since he's the judge and each bear standing in the grid has hands either on his mouth or on his eyes okay they'll play for q rounds in each round mike chooses a bear ij and tells him to change his state so if his hands are on his mouth eyes or eyes to mouth after that he wants to know the score and the score is the maxim over all rows of consecutive bears with hands on their eyes in that row the bears are lazy mike asks you for help for each round tone the scores of these bears after changing the state of a bear selected in that round oh i see okay sure i can see how this is dp i guess um wait does it change permanently does it change permanently or is it a single operation um i guess it would i guess it would change permanently um yeah okay so i guess this is the idea of the problem that you have this grid um let's use the sample and you have five rows and then in this grid you have some ones and zeroes as the problem gives um okay so use orange for one that's what it is right it's just everything then everything else is zero and then what you're interested in doing is i suppose you want to make it so or rather you'll do something like um like this i guess wait what i don't understand so it's one one i got one for one one four two okay so basically here's the idea for each row independently find the longest streak of ones in this row that is like the longest consecutive group of ones so for example this group is one this group is one and this isn't a group of ones so it wouldn't work so in this row the answer would be two because you have two ones in a row in this row the answer would be one that's where the answer be two this row the answer be 1 and that's where the answer be 0. and then over all the rows for this value you want to take the maximum of these and that's your answer for a query yeah the mic is bad i know i'm i don't have a fix for that right now this is just my laptop mic um oh wait okay okay uh sorry to this pin message will lit will like let you link the thing but um to open the mashup you have to click this in the description first and then you can it'll invite you to the contest and then you can open whatever you want from it yeah you have to um be invited to the contest first you can click that link in the description yeah i'll upload the video later so if you want to watch top coda right now that's like fine i won't stop obviously i won't stop you but this uh will be available later on so if you missed this it'll be there later yeah just like the last one and in fact you can also find the last one in the description if you uh missed it or something oh yeah by the way i forgot to do this i'm going to update the subscriber count because that's a normal thing we do um okay and so each query is basically you change a single thing you change a single cell either from one to zero or zero to one now i guess the idea is if you you have 5 000 queries and and an m or 500 so if you were if you were to change it and then recompute this whole thing every time it would be 5 000 times 500 squared which is uh too big i suppose might actually pass the time limit but it seems too big yeah so in brief the problem is you have this grid of ones and zeros for each row independently find the longest streak of ones like the longest consecutive group of ones and then over each row take the maximum of these longest groups and then that's the answer for a query and a single query is changing a single value either from a one to a zero or a zero to a one yeah so the basic idea is like consider that we do it for each row independently then if we change something in a single row like it only changes that row none of these other values change that's the basic idea so if we change it for a single row we only need to recompute the value for this row so this is of um o m the number of columns and then this value can also change for example after this query this value becomes two and then then we can just like take the maxim over everything once again naively because we only have o of n rows and so it would each query would be so b each query would be n plus m instead of n times m which is much better um i suppose that's the idea of this problem so how do we compute this well we just need to solve the 1d problem of what's the longest group of ones and to do that we can this is where the dynamic programming comes in i guess let the um let the let's see how would i word this let the value here should we we're doing this dynamic programming style so first let's identify what we're even trying to compute we want to find the longest group of ones in this array right so one way to do that is to fix the ending point of the groups of ones and then find for each ending point like the leftmost point where there's still a group of ones and that will give you the longest group of ones that ends here so that's the goal instead of doing it overall just do it for like a specific like an ending point all at once and so you can define a function f that takes in index i and it's the longest longest group that ends at i hear my mouse clicking furiously so f of i will be the longest group ending at i group of ones so if if this value is a zero then like like this just is zero because they're like you can't have a longest group that ends here if there isn't even a group at all to begin with there's just no ones here so if if ai is zero then f of i is automatically zero otherwise either you have this individual group of ones or or you can do better you can extend some previous group to the left and then have this be the end of that group so now instead of finding the longest group that ends here we're in just well we're still doing that but we're interested in the longest group that we can extend from the previous index and of course we want the longest group so it's the same as asking what's the longest group that ends at the previous index which is literally what f of i is and then we add 1 because we're extending it so if we have a 1 then it's equal to f of i minus 1 plus 1 because we're extending some group that ends before here and then we're adding one because we stick on this one to the end of it so the longest previous group is just the definition of f of i minus one and then we add one because we stick on this one so those are the possibilities and this is sort of dps because it's building off of previous answers in fact it's similar to like the second problem or something pretty sure that's what it was so um i suppose that would be it yeah so we compute this and then like the answer for a row is just the maximum over all f of i because we're like solving for all ending points so we have to consider all of them right so here we um we do this for every row and then we get this value and then when we get a query we only recompute it for a single row so let's do that um let's see so we store a best array of size like bigger than n and that will give you the best in each row nmq written the queries then just like do the stuff i i can't type um yeah i did do the sub count it's up to uh almost 5 000 now so now i'm gonna make a function called solve row because each row is independent we can just kind of like do it independently hello let's see this would be the row index i then llf we basically compute this function for this row so um i'm set all right f of 0 equals 0. this is just for implementation convenience since that way like this value for f of one would be um like simple oh yeah if you can't access the contest what you have to do is you have to click this link first because it makes you open it yeah oh wait i can i can't edit messages this is annoying oh i'll make that clear the next time we after we finish this problem and i pin the next one i equals one i is less than or equal to m i plus plus we're going to compute this f value so if mat i this should be j actually j minus one this is the value at this row in the matrix just like this if it's equal to zero f of j is equal to zero otherwise we use the recurrence so f of j is equal to f of j minus one plus one and then we keep track of the maximum overall f of j and then we say that the best value in this row is equal to the answer so now we initialize it like this and then for every query we only recompute a single row so therefore we only need to call solve row once for every um query so what do we do we read in um rc then um matt r c is flipped we can say that's like xored with one yeah it's not exactly dp i mean it's kind of a stretch but you can call it that because it still depends on previous sub problems so net rc is xored with one which basically means just flip it zero to one one to zero and then um so we resolve the row for r x equals zero then for each row ants equals max ants best uh j and then i'll make the rest of these j too in brief figure out the value for each row then this is just taking the maximum over all of them nope go to the directory first and so seems right let's make sure read in the values we're in the matrix solve the rows initially read in the values solve the row um like resolve the row because we changed it like find the answer and compute the values for each row some of these aren't exactly going to be dp i mean you can do that one with something like two pointers also but you could argue a dp solution for it okay this one is like the least solved which means it's probably going to be fun so here let me um let me unpin this current problem j you can send problems after if we have time but right now no right now i'm like not doing requests um current problem j right now pin that way it should work helga hufflepuff's cup i can speak tmw aurors i agree okay harry ron hermione have figured out that hoga hufflepuff's cup is a horcrux through her encounter with bellatrix lestrange what do you consider as better because like like big techniques that aren't used very often are like annoying i don't know anyway i'm not sure how these problems are yet so perhaps perhaps not um okay through encounter with bellatrix lestrange hermione came to know the cup is present in her family vault right the wizarding bank is in the form of a tree oh interesting with total end vaults where some each vault has some type a tree isn't yeah a tree is an undirected connected graph with no cycles um the vaults with the highest security are of type k and all vaults of type k have the highest security ah okay also the vault is of the highest security its adjacent vaults are guaranteed to not be of the highest security and their type is guaranteed to be less than k interesting and there can be almost x vaults of highest security and x is at most 10. how does this mean so harry wants to consider every possibility what oh okay okay every possibility is that he can easily find the best path to reach your vault so you have to tell them given the tree structure of gringotts the number of possible ways of giving each vault a type so that the above conditions hold this is weird why k why not just like m that's annoying um okay let me read the rest of the constraints and make sure i have this right so um ah this is annoying isn't it all right let me get rid of the scribbles this is problem j i'm going to put that here it's this problem wait this is problem j and yeah i just started another problem so it's not that big a deal um you have a tree here let's say something like this i don't know make it deep because it kind of has to be all right some sort of tree and you want to put some labels on this so you want to put some labels so that each label is at most m and there are at most there are wait exactly or at most at most x vaults that have or at most x nodes that have label k and then another constraint is that everything that's adjacent if you put some if you say this thing has label k then like for some reason first of all you can't have adjacent things that are k and also everything adjacent so like this one and this one has to have a value less than k so this is less than this is less than k and this is also less than k so given these weird constraints you want to figure out how many ways you how many ways it's possible to assign labels to fit these constraints okay um so this is a dp contest and therefore we're going to use dp and the way we use dp is kind of like weird i'm pretty sure it is pretty sure it's some sort of knapsack thing that's my idea and i'll tell you where that comes from in a sec so the basic idea is we want to find some state for this dp and this the classic sort of 3dp state is some subtree so for example what's the answer for this subtree okay convex whole trick is like not suitable for this stream we're i'm barely getting into 3dp right now if you wanted hard dp more people should have voted for that so um yeah comics whole trick is hard but anyway so for for some classic 3dp problems you essentially want the state to be some sort of subtree so that is what's the answer considering only this the people want me to continue this mashup that's what the vote said supposedly yes well also because it's going to get me the most views that's like how it works so solving for this subtree only what's the answer communism like giving the channel away to everyone for this subtree what's the answer um that's a good question it turns out this isn't enough because like there are multiple possible things a single subtree could represent like for example um this could be a thing of node k in which case we have this constraint that this has to be less than k specifically but at the same time that's equivalent to this not being a node that has k and this could be the node with k and then this can be anything but if we only store the subtree information then both of these are equivalent so we don't have enough information so what we need to do is we can't only store the subtree as a state um so for example say we're trying to build this dp formulation where we have dp of v that is for this vertex v what's the answer for it and everything in its subtree and um it's not rooted but we'll just like root the tree arbitrarily at node one or something that makes it simple then we're interested in everything in this subject the number of ways in this sub tree then somehow we combine children okay now the basic idea here is that we need more information than just the vertex what else can we do we need [Music] well for example one of the distinguishments we need to make is that is this node value k or now because if it is or it isn't that affects what we can do to this node so we need another flag that basically says is this node value k so dp of v and also um what do i call this like a flag or something but then there's also something else because we need to make sure that we only have at most um what is it x of the volts we need to make sure that we only have we need to make sure that we have at most x of the volts right so if we have two different subtrees like say say we use um three volts here and then we use one vault here and then like the total x is like two or something then that's a problem we can't do that but like it's if we only store this information then using three volts here is an equivalent state to using only like one volt here for example so with only this information we can't determine how many volts we made which means we also need to store not only this and the flag but also the number of vaults [Applause] so it's v the number of vaults and this a flag representing a flag representing whether this node is known and i claim that this is enough like this is enough information because tmw disliked because i'm better than him i made this diagram my discord that shows like how rare the beating human kickstart thing was so if you join my discord which is in the description you'll be able to see that you know by the way it's time to plug the discord here right here you can join it and then it'll be like annoying and the discord is terrible so everyone can um cringe with me that's the idea it's like an anti-plug all right so whatever's happening here this is enough because the only thing we care about first we have to care about the vertex um no there is there is a strong comparison like he's just better than me a lot in many ways i will i will admit that myself right so and then we need the number of vaults here and then we need a flag now in terms of the problem statement like the way to get the state is usually to determine what we need from the problem statement from the problem statement we have a bunch of constraints we have we have at most x vaults and we have the adjacency constraint but there's nothing else so there's like no other kind of information we need to store because the problem statement says this is enough since there's no other information the problem statement requires us to have so that's how we can tell what a state should be it depends on the constraints of the problem because we have the constraint that we can use at most x vaults we have to have that in our state because that's a constraint of the problem because we have the constraint that adjacency is like make things weird we have to have that in the state because that's part of the problem that's the idea i'm not the goat like by definition i'm not you could like sum up the number of times tmw has beaten me and the number of times i've beaten him and it would be like ten to one or something like you can't you can't say things like that yet i'm not that good compared to him at least that thumbnail was strictly a joke okay um how's this gonna work so well my discord is terrible all right how's this gonna work so um the transition seems fun here because there's like all right how do we do this transition this is annoying we have this node here and what we want to do is like say we're solving for this node we need to combine the answers of the two sub trees so let's say we have an arbitrary number of subtrees then say we're trying to compute dp of a and b or like let this be node v then we have dp of v and a and b so the question is like how the hell do we do this all right and actually a better question is how the hell do i explain this um we have essentially we can take any number of things from here here and here but so the idea is um it's case work say we have this flag b1 which means we're going to make this equal to k then that means like the only states we can use are ones where none of these are equal to k otherwise we would have the adjacency condition then she was even more annoying than i thought okay there's actually i was wrong there's actually more we need to store um i did i insulted this cord so because there's something here if we're going to make this k then if we're going to make this k then what we need to do or sorry if we're going to make this k then we have to have the constraint that all of these values are less than k because otherwise i wouldn't satisfy the problem statement so this is more annoying than i thought and i thought and i already thought it was annoying enough so this flag actually has three possibilities it's less than k it's equal to k or it's greater than k because all of these are in all of these like matter we need this kind of information so we need three different things okay i'm uh i have to figure out a way to explain this transition that like actually makes sense so um transition is assigning less values to subtrees in the current node no it's like we're sort of given the values that we put in these subtrees assign a value to this one and find the number of ways like we know the answers for these sub trees and we're trying to figure out the answer for this big subtree so we assume that these sub trees are already predetermined and therefore the only thing that we can change is this one this is like really annoying this is very annoying um very annoying to explain i'm sorry for this well it also matters if it's less than k now because if it's not less than k then we can't put a node right above it so there are three possibilities a node is less than k actually let's solve for that this is going to be the hardest part to explain i think so i may have to reiterate because it's kind of confusing say this node is going to be less than k so its value is going to be less than k therefore this state is going to be zero actually implementation isn't going to be terrible the worst part is explaining this right now i think that's that's how it is right now so this value is going to be less than k how many times have i said that now so that means whatever these values can be anything really because the less than k means that this can also be less like this um this node it can also be less than k because that's fine it can be equal to k because it's allowed to do that because this is fine and it can be greater than k because it's also like chill so um therefore we're allowed to take from we're allowed to take from anything x comma actually not x let's say another node y comma another node another value like c and then anything so a star would mean that all possible values work and we need to pick some values out of this to um to like make it so this sum is equal to a so if you see sort of a similarity between let's let me try and rephrase this so what this is saying is to find the number of ways to have it so we've used less than a things is equivalent to saying is equivalent to saying how many how many ways are there to essentially um like for example we know how many ways there are to use two we know how many ways there are to use two um what will they even call it again two high security vaults like that are equal to k in this one let's say we have a d number of ways and we also know for example how many ways we can do it here one e and like zero f or something and we know that for all of these so we're trying to find the number of ways we can um pick some of these values that sum to at most k or at most x the parameter x of the problem and so i'm not sure if you see the relation here but this is knapsack that's what this transition has to be we have a certain cost and a certain number of ways of choosing that cost and we want the sum of costs to be less than a given number or less than or equal to a given number that's what knapsack is kind of in a sense it's like it's it's not exactly knapsack because it's not the like the sum of costs but it's a similar kind of number of ways thing so within this transition we have another dp problem that we have to solve and that's what makes this so annoying that within this transition let's say we sort of like tack on these nodes in order in some order then we have this other dp occurrence i'm going to use a different color i suppose we have this dpr occurrence um what other color do we have so dp of i'm going to say u u is the current node we're at in this list of nodes that we're going through what what's happening in this chat okay we have dp of u and the current number of things we've taken let's call it z all right um dp of u and the current number of like these things the um high security vaults that we've taken and so the transition would be when we have this we consider all the possible values and then we say for example if we have the state like 0 and then f then this would add to um we'd essentially like this state would push out to the next value and then also the number of taken because we don't take any more and then we multiply that by f um and the same kind of thing here if we have this state one and e where we have e ways to make it so we take exactly one thing then we have this like goes out to u plus one and then the number of taken but we have another taken one so now it's one should we have slow mode is it isn't necessary i don't know and then for all of these possibilities for all of these like number of things we've taken we sort of push this dp out to future states or we can do like whatever kind of dp you want it doesn't really matter it's just like this for currents so the number of ways to be at the next vertex having taken one more than we just took here it's the number of ways we can take one times the number of ways we can do the rest of it so it's going to be um for example the value e times this dp value will be added to this value so it's very similar to knapsack um very very similar have we even seen a knapsack problem on here before not sure if we have do you guys want me to go over knapsack too and what that is or is that well known enough that i don't have to because knowing knapsack will make this transition make more sense because it's very similar what do you guys think is anyone alive in the chat what is one to one right now anyone else three to two okay it's like very even right now you know what for the purposes of education i'll just do it oh wait yeah okay i'll do i'll do a quick overview of it it shouldn't take that long probably so the idea with knapsack is we have a bunch of items we have a bunch of items that have a certain number a certain weight like for example two three seven five and we they have a certain um cost to them too so for example three seven one two and essentially we have this like total capacity like 13 or something and we want to pick some subset of these items to a maximize the sum of their costs so for example the sum of these green values and simultaneously their total weight must be less than or equal to this capacity that's the problem of knapsack the way to solve it is essentially dynamic programming our state is what's the best what's the best answer we can get given that we've used the first i items and that the total weight or the total um capacity we've used so far is j for example then the transition is simple for this next item for the i plus one item you either take it and then you either take it and then you get um and then you get like what is it so let this be the cost and let this be the weight then ci plus dp of ij well kind of like um like this value dp of i plus 1 j plus a weight j plus the weight of i you consider this value in that so you can think of it the other way too the dp of i plus 1 j relies on dp of i and j minus wi if you prefer to think of it if you prefer to think of it that way and then like the basic idea is just that this is the information you have and when you take this item this information gets changed so you get a new you go to the new index and at the same time you have a new weight specifically the weight you gain from taking this one and so you can also just not take the item and then in which case you have dp of i plus 1 and the same weight that's the essential idea of knapsack i suppose if this notation doesn't make sense to you you should probably see the first topics um knapsack with weight capacity up to 10 to the 9th that is interesting are there any other constraints like the atcoder one i'm pretty sure there's like some weird solution for it like i remember seeing some kubeforce's problem but i don't remember what it is so i'm not sure it's some dividing conquer kind of thing oh by the way the answer would be dp of n where you consider all the items and any j where j is between 0 and the capacity that is 13. you consider that because you can have any capacity as long as it's less than 13. okay well the accouter one is different because the act cutter one has the um i'll i'll pull this up later maybe but the accurate one has the other constraint be tiny like the costs are tiny so you can formulate it as thinking of the minimum the minimum weight to obtain a certain cost and then see if all those are possible what would default weight capacity be okay anyway that's knapsack in brief kind of so this is sort of a similar thing except we're counting the number of ways instead of minimal cost so either we um either we take the certain number of items or we just don't and so if we do then we get a new sort of capacity and if not then we just simply don't take it um that's how you would do these transitions now this is only for a zero well actually sort of no matter what you do you want to get these values like you have this many ways to make it so you've used two things you have this many ways to make it so you use one thing you have this many ways to make it so you use zero things and then this final value all these will be multiplied by the number of ways you can have a number less than k which is to say it's k minus one okay now this is one case the next case is if this value is one in which case this value is equal to k i'm going to cross this out instead of erase actually now i'm going to erase in which case this value is equal to k and then there's some other stuff going on here for example okay now what does this mean about other values what it means is that all of these values below like this one this one and this one by the constraints of the problem all of these values have to be less than k for this value to be equal to k otherwise like this just what the problem says if you have this k here the adjacent ones have to be less than k so what that means is that the only states you can consider for previous ones are ones where it's less than k so therefore the flag must be zero right and then that's essentially how this would work and then there's only one possibility for this value it's equal to k so there's only one thing you multiply the knapsack by and um how bad are these samples oh my god they're all size three what the hell oh this is gonna be so painful and um okay well there's one final part the final possibility is that we have greater than k and therefore this flag is two so then the possibilities are well we don't we none of these can be equal to k because the problem statement won't let them be since this would have to be less than k for that to be true so these can be either less than k or equal to or greater than k because either way that's fine so this constraint is that it's not equal to k which means it would be it would rely on the states 0 and two and then the number of possibilities would be um what would it be indeed it would be m minus k that's the number of ways to have that happen so in total if the flag is zero then we multiply by k minus one because that's the number of ways we can make a value for this one and then we rely on previous values dp of any y c and 0 1 and 2. if we have flag 1 then we have exactly one value because it can only be equal to k and we rely on the previous values dp of y c and one no zero every value has to be less and if we have two then we have m minus k possibilities that's just the number of numbers less than greater than k and then we rely on dp values y and c and um 0 and 2. this is organization for myself because now it's time to write the code for this how fun is that i am almost certainly going to get wrong answer on this one at some point so that's fun isn't it all right so all this is preparation for the implementation let's do this okay so first we read in the values vector edges up to 10 to the fifth then for each edge edges u push back key and do the same yeah it's definitely going to be fun now um c into k into x so now we define this function dfs a vertex and its parent so um here we would dfs from the root zero and then the parent would be nothing and then um okay i'm gonna do everything except for the like dp part first so the final answer would be well we actually don't care about anything here what we really care about is like any value um like any value that's between 0 and x and this can be anything so the final answer would be um what's the module yeah the final answer would be dpij modmod now the question is how how do we do this all right first we define the dp we need one for every node then we have at most that many possibilities from zero to ten and then we have three possible flags i'm gonna make this slightly bigger just so just to be safe doesn't actually matter alright first um for i equals 0 i is less than no what for each child edges b if x is not equal to p then dfs xb so initially we have this state dp v let's do this better um topic stream may or may not be a weekly thing okay so the way the the topics work is like i know i know youtube kind of sucks and this setup is like terrible but the way people actually vote on topic streams is i have this thing called a community tab and then there are like polls here but for some reason if you're not on mobile it doesn't tell you about this so like this is where the polls are so you can vote here and stuff and stuff but apparently like it doesn't tell that to most people which is really annoying that's why i want people to join the discord so that they can get notifications about stuff like this and you know you can join the discord here so it's like yeah it's weird like it shows you community posts on mobile but you can't see the community tab it doesn't show you the posts on here but you can see the community tab on here i'm pretty sure it's just like an absolutely terrible system honestly but yeah topic streams will occur sort of pseudo frequently now join the discord only for notifications you don't have to chat you definitely don't have to chat in fact i don't recommend chatting don't recommend chatting at all in the least so what's the idea here that um one second i did send that okay right sorry so um the idea with this is that we have to do this i'm not joking about the discord so we have to do this sort of subdp and basically this value is at most x and this value or right now um let's see so ll sub dp and so this value is at most the number of children of this which sums to o n in total so the number of children is upper bounded by the number of adjacent nodes the degree so we can do like edges v dot size plus one and the other value is at most x so it's x then we set it to zero and we say if we've taken nothing then there's exactly one way to have it so we have um taken no special nodes yet and we haven't considered any nodes yet so um all right this is fun now so first wait how exactly are we doing this okay actually i guess we're doing this for like each individual thing all right there's some way to implement this and there's some way to implement this that i do not know of i think we do this sub dp three separate times i guess for each possible flag so let's first do it for flag one i'm going to do this sort of scope magic to make it so i can declare this every time without having to um actually no i don't need to do that i guess yeah i can just do a mem set i suppose well i'm still gonna do the scope magic because it's kind of convenient then for every sub tree what we do is um four lx edges v if x is not equal to p hello count equals zero now what we have to do is we have to push these values out to the later ones and so the way to do that is to first we have to fix the number that we've taken so um a little taken is equal to zero taken is less than or equal to x than that consider all of them then um we also consider what do we consider yeah i know i know i know like top card is going on right now but i i'm doing this now because i don't have any other time to stream this week it's like it just has to be inconvenient it's kind of annoying that way i didn't even realize top coder was going out until yesterday but i don't have any other time anyway yes we can root at any node it doesn't matter we just need to we just need to have some sort of way of defining a subtree and that's why we root in an arbitrary node oh by the way um the scope magic is basically saying like like you know how you have four loops right and these kind of just have their own scope well i'm doing this but without any sort of loop so it defines a new scope but like for no reason kind of except the reason is so that it can be its own sort of thing okay um it's all right i'll occur taken equals zero i've yet to figure out the complexity of this program how how is this a 2000 i don't understand so then this is the number we're going to take um if per taken yeah i use it so you can use local stuff except i'm not actually doing local stuff so nothing really makes sense but i'm going to basically copy the same code three times so that's why i'm doing this just so there isn't any sort of copy copy paste there um although total equals the number we've already taken plus the amount we're about to take if total is less than equal to x then continue and say that and actually if not then we can break because we know that like this is only going to increase actually we can say take is less than equal to x minus curve taken and that works too we don't actually have to check this um l of val is equal to so for this flag we define it like this because we make this value less than less than k we can have it so any of the previous values in the subtree can be anything we don't care what they are so it can be 0 1 or 2. so therefore it's sub dp count zero actually how'd this work it wouldn't be subtle no it would be um dp of x and then take no okay this should not be x my bad this should be something like y the new node that we're using that's a bit confusing so this should be y this value should be x this should be x this is the next this is the child number considering and it's this plus y take 1 plus dp y take 2. in fact this is the only value that's going to change in the three things i'm copying but i don't see a better way to do this so um i'll just leave it as so then and how would you do this going to be the new sub dp count plus one and take and now this would be the total this is the new amount we've taken equals sub dp count plus 1 total plus the value the number of ways we can take this many things from this node times the number of ways we can take it from like the previous configuration or like the number of ways we can take it from the first from the first this many nodes and then times this one which would be sub dp of count and the current number we've taken modmon what right let's check this so this is the current amount we've taken we ensure it's less than or equal to x this is the amount we're going to take we ensure that this sum is also less than equal to x then the value we have is simply all possible things we could have taken from this node because this value is going to be less than equal to k plus one and then this is going to be this it's the number of ways to take it from this node specifically times the number of ways to do it from the rest seems legit um okay now we do the final parts for lli equals zero is less than equal to x i plus plus sub dp count i equals sub dp count i times k minus one and this is necessary because there are k minus 1 different values we can have for the current node that we're at this can be any of k minus 1 different values if it's less than k so um and then somehow we do this here then we say actually this doesn't even have to be sub dp this can just straight up be dp of v i and the flag would be zero because that's that's just that's what we just computed okay this that that is painful but that's the worst of it i believe so now it's almost the exact same thing except we changed like two lines or so and so if i end up getting this wrong i'll have to change everything once again all again so if we're going to make this value equal to k then there's only one possibility for this value and the other thing is that we're going to only rely on the values that are less than k because we can't have it be adjacent to anything else so this is that and then the next value is flag equals two where we have um we can rely on anything that isn't equal to k why take two and essentially now this is going to be the number of values is m minus k because that's the number of values greater than k but less than or equal to m right and then this should be two and this should be one and i suppose that's it oh i should increment count this count is the number of nodes that are not parents and i can't do a normal for loop because the parent could be part of this adjacency list and i have to skip it in that case all right let's try it ants equals ants plus dp um zero the root node i have to test this with some stronger samples okay it's wrong already great what else does it work for does it get zero at least here it does okay right so what the hell is this sample then we got three nodes like we failed a sample of size three how sad is that we got three nodes um one two one three and we can have the value of k is 2 and we can have most thing at most one thing so what exactly is happening um now we debug i one x j so essentially how many ways does it think we're finding for each node oh right wait what did i do yeah okay so actually i forgot that this is like this transition makes another node with k so therefore this has to be that we take one more which i kind of forgot about i'm actually like not sure how to do this at all yeah that i don't understand how did that work how did that work at all all right normally in contests i would use stronger samples to test this but because this is like yolo whatever i'm just going to submit this so we're going to be wrong so i'm going to try and come up with more um samples oh we actually got it wow that actually worked is the stream buffering oh come on obs what the hell i believe in this all right well that's that was that problem that sucked let's do something better um let's see okay so i've done what have i done i've done this one i have yet to do this one with dp so um okay i guess obs is just glitching sometimes i get to do this one with dp so well i'll try and do the dp solution for this all right that was j now this is problem l and i will edit this message let me click this and this is going to be problem l can i add this anymore no i can't somehow i'll find a way to be more organized about this but not yet okay i suppose that's cool okay innovation techniques are on a victorious march around the planet they integrate into all spheres of human activity a restaurant called dijkstra's place has started thinking about optimizing the booking system there are end booking requests received by now each request is characterized by two numbers um ci the size of a group who will come via this request and pi the total sum of money they will spend in the restaurant you know that for each request all ci people want to sit at the same table and are going to spend the whole evening in the restaurant in the opening moment at 18 o'clock to the closing moment okay unfortunately on the k tables each table has a maximum number of people that can sit at it each table can only have people from the same group that's nice if you cannot find a large enough table for the whole group then all visitors leave and naturally pay nothing your task is to decide which request to accept and which request to design so that the money paid by the happy and full visitors was maximum now i told you i have solved this problem in a dual but the way i did it was was with a greedy and it was like not good so i'll use the same principle but we'll do dynamic programming with it so i will show you how you can use dynamic programming to solve this problem and really like even if a problem like even if the main solution of a problem isn't dp if you can still apply dp to problems that aren't like obviously dp and if you can still make that sort of like thinking and do that sort of thing then you'll like definitely be able to apply to problems that actually are dp so even if a problem isn't obviously dp you can still practice it by trying to use the technique on it that's why even though some of these problems aren't necessarily dp problems they could still be useful per se i'm gonna make this bigger uh how long am i streaming for maybe like um around one or two more hours it's not going to be as long as last time because i like have some other things that have to be done but i can go for a while i suppose by the way 5001 okay um yeah this whole thing was fun you can get rid of it now i'm actually very very surprised that i didn't get a wrong answer on that very surprised all right so the basic idea is we have a lot of people here um each person is i have groups i do have school but not on wednesdays normally which means that today is find a stream that's the reason today is the only day i can stream because i normally have school on the other days dedication okay well that's arguable my dedication was more explaining how to solve like i had the solution but the dedication was about explaining how to solve it than anything else because explaining like a knapsack transition is hard okay so the number of requests from visitors then end lines follow right so you have a bunch of tables each table has some sort of capacity let's say for example 4 6 and 9 and you have a bunch of people each person has a size right each group has a size and for example 10 and 50 and then 2 and 100 and 5 and 30. you can match any person to any table as long as there are enough seats at the table to fit all the people dynamic program is daunting did you have trouble solving basic problems i did dynamic programming took me like months to learn and use good training mostly because there wasn't enough there weren't enough like problems to make it solid solidify and i just like didn't know what i was doing for a very long time um yeah okay how many months maybe like there's something like one or two like i was actually trying to learn it's hard yeah dp is not an easy concept like it's not easy to learn i'm trying to do this stream to give a bunch of examples but no matter what it's going to be hard to learn that's kind of um it's like hard doing sponge but struggled to come up with your own solutions that's kind of i don't know i feel like if it's that case you should put more time into it because it's better to like have the thought process of trying a ton of things and um like i mean eventually something's going to work something has to work so the more time you spend thinking on a problem the more um like the better of a thinking process you'll have in general that's the way i see it bitmasdp this problem the third one was bitmasdp you can see that on the previous stream if you want and the previous stream is both on my channel and in this description i'm not sure if there are any other bitmasdp ones but i know that one is okay okay okay okay back to this problem so the basic idea is let's say we have a match up like this where we um first let's sort the tables or let's sort the groups and the tables by their like um values or by the the people that they can require and also store and apparently that cut it off for some reason say we have something where did that go there was like a piece of purple that just disappeared from here supposedly how long do i try and solve a problem that depends it could be like anywhere from hour to multiple days sometimes that was my um philosophy for use code training at least div 2d yeah i can try that after this if i got through these quickly enough okay right so the basic idea is you have something like this and you basically want to assign as many of these to tables as you want so let's say you have some assignment like this right then like this assignment sort of like crosses the paths of these two arrows so therefore you assign the higher one to a lower one and you assign the lower one to a higher one but if this is possible then you could do the exact same assignment but you could assign the lower one to the lower one and the higher one to the higher one and this may in fact be better because then it leaves you like more sort of freedom like you can assign this higher one to more possible things so the argument is for any like like consider some optimal configuration like consider the optimal configuration where you have some sort of cross paths like this then you can instead change that optimal configuration to not have cross paths so therefore because you can do it like this if there exists an optimal configuration which there does then you can change it so there's an optimal configuration that doesn't cross paths and what that means is that you can solve for the optimal configuration where you assign the value sort of in sorted order so like when you assign this value to something here then that means anything you assign to this one will be after this one that's the idea so you could instead do this like this and you will assign them in sorted order now this is easier because now you have something like this wait is div 2d the graph one the one with like clicks and stuff i hate that problem that problem has terrible limits like most solutions were like very very close to the time limit wasn't it will i drop to blue purple i will not actually i might unintentionally but not for that purpose okay but anyway now that we have this in sorted order that means that we can squeeze some information down to like a single part say we know this and we know the last thing we assigned was this one and we know we assigned it to this then it automatically means that like whatever we assign here it has to be after this one so we don't care about specifically which ones were assigned we only care about the position of the last assigned one so that's cool because what it means is that what it means is like um the only information we need is the current like the current group we're on and the current thing we're trying to assign to because we know that once we're here we can't assign to anything before here and we're only going to assign to anything after here so that's the only information we need and therefore the state is simply dp on the group and the current table we're at and then we can define it like this i'm going to try and do a recursive formulation here to try and like switch it up a bit is equal to the dp of either we assign the either we assign this group to this table plus the cost of this group or the um what is it the price of this group so p all right sorry this should be group minus one table minus one plus p of the group because this is just simply like we assign this group to this table so we decrease one from both of them because both of them are used um and actually it's the maximum over all this because these are the possibilities for things we can do at this point or we can go into the previous group or we can go into the previous table and so the reason we can sort of like do this sort of like subtracting one magic is because essentially like either we make this assignment or we made the assignment with some other group or some other table or possibly both but if we have to if we have to decrease in like both of these then we'll eventually do so like we can do like a minus one here and then a minus one here and then a minus one here and so to eventually find the previous pair that we used but this makes the assumption that we've used all groups up to this point or not used them and we've used all tables up to this point so this recurrence is very similar to edit distance all right i think it's what it is except now we're finding the maximum instead of the minimum is it at a distance or like longest common subsequence or something oh and this transition is only possible if the c of the group like the if we have enough people the the size of the group is less than or equal to the table size our table right okay so now we implement this um and then we make an array for the tables let's see so first i have this very basic thing that just reads into a pair reads the first one first and the second one second it's like quite intuitive then reading the tables this would be m wait what now so reading to end reading to the groups reading it's not guaranteed that any of them are sorted i suppose so we sort the groups let me sort the tables should be k then let's define this dp function so we've used n tables and k groups or n groups and k tables then we just simply do that this is going to be memoization you can do it in any way you want that i may also try like the basic table the basic like the the well-known form of dp like the one where you just do it in the loop that's also possible um dp 0 0 equals 0. so let's see first case if we're out of bounds um return some like negative huge number like 10 to the ninth if we know this value return it because we don't want to re-compute values and um so then we have three possibilities return dpn k equals max first possibility is f m minus one all right actually let's just do this if let's see so if it's groups i dot dot first is less than tables and okay then what that means is that all right it should be less than or equal to that means we can assign this group to this table essentially then what we can do is um v equals max v f n minus 1 k minus 1 plus um the value we get from it v equals max v f of m minus one k goes max v f of n k minus one then we memoize it by setting dpnk to that and this negative 1 is fine because none of these values are ever going to be negative 1. that should be f oh we have to print the values okay that's kind of annoying um all right printing the values is kind of annoying but let's just first compute the value first i forgot we have to do that okay so first we'll compute the values and then i'll i'll demonstrate how to recover the actual things from a transition um right how's this gonna work okay what am i doing wrong first of all there's something that's going wrong here not entirely sure why ultimate debugging strategy and then um something's happening somehow we like don't take this one i'm not sure why zero one what groups end up first is less than equal to tables okay so zero and one our group one and one is thirty somehow going to be thirty one and one but two and a hundred should be first oh wait this should be m minus one okay yeah right so if n is greater than zero and k is greater than zero then we consider the previous ones because those are the ones we take actually because we're zero index and that's one that make more sense now we have 80 somehow i'm not even sure how that's possible how how is that even possible there's no way that could happen what okay 1-130 there's no way that could happen um that should be this yeah oops that makes sense that would be how that could happen yeah okay now we get 130 which is fine but now we have to recover this and so the way to recover this generally is to um store sort of a parent array so like we know we have three possibilities right and so what that means is either we took it or we came from one of these so say we have this and we want to figure out how how we got this answer so then either we came from here in which case like this was our previous state we came from here or we came from here so we can store what we came from essentially we can say that if we did this we like we did like action zero or something if we did this we did action one if we did this we did action two and then we store the action we took and then from here we can figure out what the previous state was by tracing back our actions so this is generally called like a parent array or something [Music] um so let's see let's start with this and then um now we have to see we have to see specifically we can't take the maxim anymore we have to see does this improve the answer and if so then set the parent to that so this would be if val is greater than v then um v equals val and parent and k is equal to action zero so if n is greater than zero val equals f m minus one okay if val is greater than v v equals val and the parent of this is action one we do sort of the exact same thing here if k is greater than zero then consider m minus one k minus one and the parent is action two and then we just do this this will set a parent everywhere except to zero zero so now we sort of just like do this annoying thing where we gotta do some stuff so vector we need the indices i hate this problem we need the indices of the values we took and that's fun okay well we want the indices sorted by okay this is how we this this is how we do this last part now um we want the indices how are we down this far down okay we want the indices sorted by value for example we have like this 50 and index zero and we have this 10 and then this index one and this 25 and this index two then we want we can sort of create these pairs of value and index and then we can sort this list of pairs then when we we have the things that sort of value but we also have the indices that we want so that's what i'm about to do here and it's going to be very annoying because now there's like even more information we need to store group vals and the same thing for tables group vowels i equals make pair groups i dot first the value and i and we can sort these two and we do the same thing here just tedious implementation it doesn't add anything to it table vowels i equals make pair table no it uh yeah tables i and then i then sort the table vowels plus okay now we basically store the operations we did so um cur group is equal to n current table is equal to k now while per group is greater than zero or curve table is greater than zero what we're doing here is we're basically starting at the ending state and we're retracing our steps so if um let's see if the parent of current group and current table is equal to zero then we took both so um ops dot push back so it would be table values current group minus one dot second for the index and the other one would be table values all right it would be um no this would be group values and the other one be table values slightly going insane that second minus minus group and minus my square table else if par per group per table is equal to two not one and that means the last time we just went back a group so just do that else minus my square table then to restore the answer we do this and we print add one because we're zero next thing can i be done with this problem yet okay um books to improve competitive programming well good knowledge of sequels plus is good um there's some like there's some like thing here you can use i think like there's a css book or something cscs yeah you can try this i heard this is pretty good hopefully that works as a link i'm not entirely sure if it does can you see that or not or do i have to put in the description because youtube is okay cool you can't see it hopefully three two two one yep so we print the answer somehow i took all of them not sure how what i had no idea why that happened see yeah her group what what happened so we're at three we're at two we're at one somehow we took all of them even though it doesn't make sense i don't understand how this happened i guess we should make this like negative 187 or something to make it so it's not so even if we come from the this doesn't make sense ah what the hell okay i guess we're printing the parents now well no book will help you improve your problem-solving skills so you have to do to improve problem solving is like problem solve well you can go to code forces or um actually cses like the the problems go with the book so you can try that too there are a lot of things you can do but like you if you know stuff the best thing to do then is to solve problems that's the only way to that's or that's the definitely the best way to improve problem solving is to do it i'm not sure what's happening what does it think is going on like it the parents are one what does it mean i have no idea what's happening what why would that do that it's not printing the thing what is it not printing oh wait that kind of makes sense okay yeah okay that makes sense yeah that's the problem with recursive actually like you rely on the um oh this is annoying yeah okay so the reason i have to do this first is because like this parent thing doesn't work if i don't compute the values so that makes sense and the fact that the printing was out of order was an indicator of that that i was doing the things in the wrong order okay now it still doesn't make sense 2 130 match 3 with three and two with two okay that works hopefully that's enough i don't like this problem so i want this to pass um but yeah that's the basic idea do some dp restore the answer get wrong answer on test three apparently or not my answer on test twenty what does that mean yeah you can definitely start cp without like prior knowledge and stuff what the hell is this i've done some like indexing stuff or something how how is it wrong answering just 20. how do i pass 19 tests what happened ncipi right okay so let's just like sandy check everything i guess so read in the value read in the group make the the pair sorted by index then do the same thing for the tables make it sorted by index sort the groups sort the indices so the tables sort everything initialize the dp make the operations uh compute the function i guess the function would be wrong then the current group and the current table is k walk backwards through the parent thing and um and then from here we print the operations that we do and ideally it doesn't like screw us over somehow all right so if n is less than zero or k is less than zero return some massive negative value if dpnk is not equal to negative one return dpn okay maybe this should be an even bigger negative value like only 10. that could be it because otherwise it could like possibly take like the worst of actually that probably shouldn't change anything yeah okay nevermind well something's wrong here so if both are greater than zero then that means we could possibly take this as a value and we could take this as a value then if this is better than what we have set it to that set the parent to this um if currently like n is greater than zero then the previous value we can consider removing this one and then going backwards on it and we set the parent to action one and same thing for here we set the parent to action two and i'm not exactly sure that is annoying so if this parent is zero then make the operation with like this and that if this parent is one then go back in the group otherwise go back in the table maybe maybe i think there might actually be some other issues starting okay maybe the issue is that like if there are tables with the same value oh that's so annoying if there are tables with the same value but like different like benefits like for example a 50 a 50 and like a 10 versus like a 50 and a 1000 then like maybe it's giving it the wrong value sorting by ignoring this might make it so we take the 10 instead of the thousand i think that's what the problem is and that's so annoying but not luckily we don't actually care about that i suppose okay yeah i guess that's what it would be so we did right yeah is that fixing yeah wrong answer somewhere else okay we got that problem we have three left with my limited time frame i'm not sure i'm gonna be able to cover all of them but i will try um let's see okay first i'm gonna go to the bathroom i'll be back all right to be right back again make my own sort of cover screen and like a check mark i don't know i'll see you guys in a second all right our turn hello everyone i'm not sure what i'm gonna be able to do i have like maybe an hour an hour a half left so i'm not sure if i can get through the rest of this but i'll try solve div 2d maybe if i have time i mean i want to finish this mashup that's the ultimate goal for this stream i'm not sure if i can but i can try shall do um this one i mean is div 2 ddp it like isn't right div 2d is this like graph one where you have to find a click and stuff isn't it it's like very annoying it's very annoying because the time limit's one second i have three left we'll see we'll see we'll see um right all right well the idea for this the idea for that problem is the idea for the div 2d is that you just like you remove all nodes that have degree less than k minus 1 because otherwise it's impossible like you can't use those nodes ever so get rid of them and then while you still have nodes that are of degree less than k minus 1 get rid of them now all nodes have degree at most k minus one um yeah i could link the invite too that's true but whatever actually i'll cover that problem like after um since it's like i can't just explain it without any sort of visual because it's a graph problem sure i could link the mashup actually that's kind of smarter although i'm not sure if this huge like invitation actually wait maybe that'll work let me try that does that fit it does fit okay all right cool so all right whatever is going on here do i have notes i don't know okay so this problem m recently arena arrived to one of the most famous cities of berlin the berlatav city there are end show places in the city numbered from one to end some of them are covered by connected by one directional roads the roads in broad top are designed in a way such that there are no cyclic routes between show places so it's a tree initially arena stands at the show place one in the end point of our journey is the show place and is it a tree how does this work there are no cyclic routes so it could be a forest wait what oh is it directed okay it's directed in my mind so it's a directed a cyclic graph my bed let me show you arena sensor show place one the endpoint is to show place n she wants to visit as many show plays as she can however her stay is limited she can't be there for more than t time units help her determine how many show places she may visit during her journey from show place one to show place n with the time not exceeding t it's guaranteed that there's at least one route from show place one to show place n such that arena will spend no more than t time units passing it um is this dp how many show places should we visit okay memory that's annoying all right so this is my interpretation of the problem statement i hope it's right you're given this directed acyclic graph which you can represent kind of like kind of like in weird representation niche and you have this node 1 and you want to get to node n and so acyclic means that there are no cycles so like um there's some order in which you can visit the vertices so that like there are no cycles or something so for example like this i mean like you can sort of assign every vertex a height and then this height would be like actually this is a bad example um do it like this i suppose and then this would work yeah okay i guess so whenever i try and think about an easy problem do i guess the solution i mean sort of that's the power of intuition like for easier problems they just kind of like go down quite easily because most of them can either relate to previous ideas or it's just intuition like powers through it like there will come a time where you just see a problem you look at it and you just know the solution instantly whether it be a topic or some sort of math thing but that will be that will be what intuition does that's kind of what happens with when you get to a certain point which is why sometimes it's like hard for me to explain how i solve easy problems because most of it's just experience and that you can't really teach let me make this a thing too now this is an edge okay right now we're interested in um so each edge has a weight let's just draw assume these edges are weighted like with whatever then you want to find essentially the longest path from 1 to n that uses [Music] no more than t units okay so the fact is n is small and it's like 5000 which is nice because what it means is that what happens is that um like we can go here how does this work okay there's something with topological sort here but i don't want to explain it like that so i'm going to try and explain it a more intuitive way i guess say we're like here or something and we want to find the longest path that uses like not many time units of this well n is small so what we can do is in sort of a in the dp fashion of storing some information and keeping track of like others what would we want this state to be first the state has to include a vertex that's just always how it works so a dp of vertex but then because because n is small and this is a directed acyclic graph meaning there are no cycles any path is going to be at most length n so even though the time values are massive we have 10 to the ninth time values like there's no way we can ever store that in terms of anything we can instead store the path length that we use so we we're interested in getting to this vertex having visited this many vertices in the past and the information we store is then uh one second the information we store is that yeah the information we store is that like we store the um minimal time or like the minimal total path length to get to here so we fixed the vertex and we fixed the length and then we're interested in the like the the least amount of time we could have used to get to for example here having visited two vertices so minimum time now this is nice because say we know this information for um like position n then say we know we know um t equals nine and then we know we can get with one vertex in three time units we can get with two vertices and seven time units and we can give it three vertices in ten time units then we know that we can't have a path of length three but we can of like two because seven is less than nine and so in total what we what we do is just we um compute this information over all vertices and then essentially we can use that in a dp manner to compute it for future vertices now the hardest part in doing this is figuring out what order to do this in because like here's the problem this is not an array it's harder than an array so we're computing it for um this then like there's three separate vertices this can depend on this can depend on this this and this and so like i don't think this is a good example actually i'm trying to demonstrate how this could be hard um i guess i wouldn't be never mind i'm kind of wrong i think it wouldn't be hmm recursive kind of like takes the cake here because it's nice so there's no there's not exactly a great iterative way to do this the way to do this with iterative dp will be to find this thing called a topological sort and what a topological sort is is essentially like it's it's an ordering of the vertices such that every vertex like every edge goes from a lower number to a higher number so for example it would be like this this would be this would be um a topical a topological sort like this would be invalid because this edge leads from a seven to a six and seven is higher than six so that's bad like we want it so every edge leads from a lower number to a higher number so for example this would be a good topological sort we can do something like this and the reason this is nice is because in sort of iterative dp this topological sort will give us an order to process the vertices in because it guarantees that once we get to a vertex everything ahead of it it guarantees that when we get to a vertex everything that comes before it will already have been processed that's again the whole point of finding an ordering for additive dp everything before it has to have already been processed and once we get to this point um so that's one way to do with it if the other way is with recursive and with recursive it's nice because we don't care about the order at all so we can totally ignore this whole topological sort thing and instead just um like let the recursion do the work oh wow we hit 5000 that's cool let me see let me um open youtube then there we go we did it so yeah as people may have been saying there is going to be some 5 000 subscribers special i will announce what it is later in fact i will announce it in both the discord and this community tab so you should check back on this at some point it may or may not be soon but like i'm gonna announce it here so if you check this and it's like there then it'll be there okay i think this is worth updating the sub count again because why not uh yeah let me get rid of this and then we can do this whole part so now we have five thousand we're we're even closer to um we're even closer to memory limit exceeded now how cool is that yeah casual double in subscribers that is indeed true okay so basically with recursion this becomes very easy what is the rating of this judging by the number of solves it has i would guess either um here let's find out i'll open incognito and we'll see uh 1800 okay so it's not terrible all right so basically this dp value is v ln is equal to the minimum of of all like dp of a previous vertex that means a vertex that has an edge to this one len minus 1 plus the cost of taking this edge so for example n would rely on this state and then it would be and then the extra cost would be um for example this weight that's one possibility we consider all the edges that have this and consider all the edges that go into this vertex okay in terms of transitions this is actually quite simple and then to find the answer we just check all possible things for the last node and see which ones work so let's do that we have dp of 5005 and 5005 is that going to work 5 000 squared times eight it's barely going to pass this might actually cause emily now okay okay 26 times three times eight it's barely going to pass the memory limit that's fun okay so first reading the values um so now for i equals zero is less than n i plus plus no m this means we have an edge from u to v um all right i'll read chat in a sec after this um this isn't this is the most important like we read an edge from u to v but we're really interested in how many edges go to this which means we kind of want to reverse these edges to say that we have an edge from this one to this one because we're only considering it when we're actually at this node so we kind of like reverse the graph we've reversed all the edges like so edges v dot push back okay um what happened so uh if you want to make your way up in code forces yes problem practicing is definitely the best advice past mistakes past mistakes i think my biggest mistake was getting too like wrapped up in it like taking to taking this thing too seriously honestly because if you take it seriously you're gonna get like stressed and freaked out during contests and it's gonna like totally screw up your mentality but if you go in it not caring like it's the best way to think about it because then you'll just be able to like you'll just be able to focus you'll be able to think about the problems instead of thinking about rating and like being scared and everything so i would say that is a good thing um what do i use in five plus plus to prove a point to prove a point that ide doesn't matter yeah i do have the pinned message but i didn't have it last time that's the key it told me like recently that i have this option now but it wasn't there before okay i'm gonna write this code and sort of like be more silent about it so now um yeah this should be um sure we need to print the path here right oh we do need to print the path come on wasn't what these problems are restoring the answer so first f x dot f n minus one so if if len is equal to zero if v is equal to zero return zero return only because that'd be in doubt so now we assume len is like greater than one then um if cos is less than best best equals cost and previous v when is equal to x not first is it bad practice to write top like topper bomb dp i mean not really in general it mostly works for everything certain problems like it's harder to do it a certain way certain problems that may actually be impossible but like by the time you get to those kind of problems you'll be comfortable enough so that it's not that hard to recognize [Music] um i'm 17. yeah i just use light mode because i don't like the feeling of dark mode like it's kind of like claustrophobic in a sense it's just like personal preference if it blinds all of you then that's for the better so you're welcome yeah i'm 17 right now currently subject to change in the future hopefully [Music] then we decrease the length by one so decrease curve and then zero then we put them in reverse so we have to like we constructed the path from reverse so we have to reverse the whole thing well they want spaces [Music] that's fun actually i should make these hints this is not going to pass the memory limit oh come on i can't use pre because it's a reserve word are you kidding me this is not gonna pass the memory limit and that's fine i will figure that out as soon as i make this work one two four one two four six okay i have to make these hints because otherwise it's not going to work but to make these hints it's like even more annoying because now i have to make this not long one um let's see so this can be a min what should i make it like the value t yeah i guess i don't really care i guess i don't really care what it is as long as i make sure that if it's greater than the limit then i store that so that's supposedly fine like it just needs to not overflow that's the point okay let's see if it does overflow i'm not being careful right now so it could get wrong it could very well get wrong answer and that's acceptable i suppose wow that is a high time usage what the hell how is this oh yeah it's unscored okay that makes sense uh all right what's in the chat let me check everything what did i use wait why'd i use 389 before like i basically just picked an arbitrary big number like it doesn't matter what the big number is as long as it's big enough that um it's bigger than any plausible value that could possibly like mean something is getting state by writing recursive dp and taking the variable parameters a good practice uh yeah that's fine i mean i'm doing it right now it just passed this problem in some cases it's a lot easier to write recursive than iterative like for example recursive handles the computing order for this but if you were to do iterative you would have to do it on a topological sort which is like annoying don't don't do that if you don't have to yeah negative 3 or 3 9 was basically infinity that's what i meant it as um to ddp answer to dp questions i see people making tables but can't we solve that directly um i'm not sure what you mean by that like direct like a direct relation would be like what do you mean what do you mean by direct relations um i'll check that after is it possible to get the answer if you have to do it with compressed memory i'm not sure that seems hard to do i'm not sure if that's possible um like direct relations would be dp right typing speed like 100 or something like that like around 100 maybe connected component dp i don't know what that is wait let me see if i let me see if i do know what that is this is something i know it's a non-trivial trick yeah i don't know this i wouldn't be able to explain it because i've never seen it before unfortunately what why did i get rid of the formatting wait this text like has no color for some reason that's kind of whack okay there it is all right so we got that one um we have two left supposedly this one is also tied for the hardest one so i'll try this now and also re-pin the message and everything [Music] coolio you're given a matrix a with n rows and m columns each cell contains an integer on it you can change the order of rows arbitrarily but you can't change the order of cells in a row after you pick some order of rows you traverse the whole matrix the following way firstly visit all cells of the first column from the top row to the bottom one then the same for the second column what firstly visit all cells of the first column from the top right of the bottom one then the same for the second column and so on during the traversal you write the sequence of the numbers on the cells in the same order let that sequence be s1 s2 snm so that's fun look it's not that i didn't know how to pin messages before okay it's that i literally couldn't do it i don't know what you mean like i didn't have the ability to before it wasn't like i couldn't figure it out all right okay okay let me try and um explain this problem i guess i see it i see a way to do this this is actually like this is a separate form of bitmas dp that i think is quite cool and in fact this may be exactly what some of you wanted so that's perfect this this mashup is like surprisingly um versatile like it has kind of everything in a sense maybe i'm missing some things but i see that it has a lot of things that are useful well d1a's are hard that's true i guess all right let's explain this problem so you got this like why would n be one so you have this like um this group of cells like so this group of cells wait how would this work okay i'll use the second sample i guess you have a bunch of you have this like matrix each matrix has a bunch of rows all right i'm trying to illustrate this in a non-terrible way but like let's see how to do this so basically you have values like this nine nine ten eight um five three and four three and in one move you can sort of like you can move this row anywhere you want like so you can rearrange the rows however you want but you can't rearrange the columns [Music] um that's what it is right you can rearrange the rest okay so then um and then what you do is so this traversal is kind of like this you go down like so and then back up to here and then down like so all right so like you go here and then you go here and then i guess you write all these numbers in a list so you'd write 9 10 4 5 9 8 3 and 3. and then essentially what you want to do now is you want to this looks terrible okay in zero and knapsack problems can we visualize them without making tables well kind of i mean like the table is only to store the answers that you've computed that's all it is you're just keeping track of what you've done i mean in another sense it is a function kind of like it is a function of a certain number of values and a certain number of um weight that you've taken so far and then that function relies on previous values of that function and to optimize that function what you do is you store the values of the function that you've computed already and that's what the table is for so it's kind of necessary but you don't need it to like understand the way the recurrence works i suppose um okay right so you're gonna write all these numbers out and then you're gonna take like essentially you want to maximize you want to maximize the um the minimum absolute difference between any two values so for example this difference is one this difference is six this difference is one this difference is four this difference is one this difference is five this difference is zero so the maximum so the minimum value is zero and therefore this arrangement is terrible so we wanna do better but that's the idea of it um right so the key here is that the number of rows is less than or equal to 16. now that's the key because now we can do some like we can do something's like some cool cool stuff you know the coolest is and the way we do the cools is is wait didn't they have okay now i have two thousands i guess this is the other two thousand but the way to do this is like so you say you've put the first like say you've put the first like k rows down and whatever the cost is for these rows like it's not that important what does that have some other meaning that i don't understand i just said it to sound weird like say you put all these rows down right and so what we want to do now is we want to kind of like we have this cost between these two and we have this cost between these two right but these cost is just like it's summarizable in a number this number x is the maximum or the um the minimum absolute difference between any two adjacent values and we'll kind of ignore the fact that we also have to like compare these values too like these values between the bottom row and the top row because we can handle that later but like say we put the first k rows and then we have some cost x then we put another row down the only thing we care about is the previous row essentially so then when we put this row down now we have k plus one rows okay plus one and then we continue until we put all the rows down right so if we were to sort of summarize having put these rows down what we care about is which rows we put down so far actually we care about which rows we put down so far and the previous row we put down because that's going to determine the next cost so we have some sort of state that looks like this dp of which rows and the previous row and um in terms of handling this cost the cost between the last row and the first row what we can also do is we also have to store the first row in the state otherwise it's not possible to otherwise we can't like determine the final cost so we store the like which rows we've taken the previous row and the first row previous and first are simple they're just numbers and which row can be represented like so we can create some sort of like we can create some sort of like vector that represents whether each row has been taken or not instead of having a list of rows like for example like so so this means the first row has not been taken the second has been the third husband the fourth hasn't the fifth husband and the sixth hasn't and then this would be our state for example and then when we want to figure out if a row has been taken we just like asked the we just asked the vector like has this been taken or not right so that's simple but like at the same time vectors are annoying let's do better we have at most 16 values and notice that these values are either one or zero which means that they're like kind of like binary values so what if we just compress this entire vector into a single number like a binary number that represents this value and then to ask if something's been used or not is the same as asking whether the like whether this bit is set or not which we can do with some bit-wise magic and because again because this is less than or equal to 16 this final number is going to be less than or equal to 2 to the 16th and that's the total number of possibilities we have for this state so um this is called a bit mask because we use like a binary number to represent other types of information and so the strategy in general is called bit mask dp then the transition is simply put down a new row and then ask how does that affect the cost and specifically um specifically like when we put down a new row then we're kind of interested in what's the minimum absolute difference between any two like corresponding elements in this row so like sort of a problem is that this is a lot like this is very much a lot because m is like m is like less than or equal to 10 to the fourth so if we naively compute this transition each time it's going to be something like o of 2 to the n times n cubed because we need n's we need 2 to the n times n times n states and then this transition there are n possible rows we can put down so this is 2 to the n times n cubed but then computing this is going to be also 10 to the fourth so let's figure out what that is quick back the envelope calculation or just like using the computer 2 to the 16th times 16 cubed that in itself is bad and we have 4 seconds to compensate but if we stick on a 10 to the fourth like there's no ways it's going to work right just look at that number it's so so big but like again we don't have many rows and what we're really interested in is given some row a and some other row b what's the cost between it so the idea is that we don't have to compute this cost every time in the beginning we can compute the cost between row a and row b and that'll be it we can pre-compute it and then we can use this sort of as a lookup table so we don't have to do 10 to the fourth operations each time since we've already done it at the beginning so the total complexity comes out to just 2 to the n times n cubed because we already know these values how are team sdp problems i'm not sure i haven't actually i've never actually used that site so i wouldn't know but i know like people like um nick have um praised that site before and he's like what is he now he's fifth in the world right now so it's probably good yeah it's probably good um let's see okay how are we doing in terms of everything i'm not excited to code this but we gotta do it so let's do it please tell me we don't have to restore the answer ah thank god okay we only need to print the value not not the rows themselves thank god okay awesome do so the basic idea with these cost arrays is that cost one is going to be the um the original cost the minimum of the absolute differences between the like the corresponding column values and cost two is going to be specifically the cost from like this having this row as the ending and this row is the beginning so therefore we have to compare this element with this one and we have to compare this element with whatever would be here and so on so that's cost 2. um so the values are 189. [Music] then um actually let's just do it like this cost one i j equals this then cost one i j is just do that seems good then we do the same thing for cost two we do minus one here because we're comparing this one with the one ahead so we exclude the last index cos two i j and most of these values are going to be redundant like we don't need to compute i j and j i but for convenience it's like whatever um so this is min cost two i j um abs mat i k minus mat j k plus one the next value now we um do the dp dp of 2 to the 16th we can just do 17 17. now how do we do these transitions that is a question it is in fact a good question and one do i that i do not know how to answer so that's fun yay um we have okay put doing push dpr is definitely the way to go because otherwise like we can't easily determine what the previous and the first rows would be i guess um was infinity sure actually i want to maximize this so we can just make it zero in fact no this was necessary okay now first we check if this state makes sense so this state makes sense if first of all the rows aren't equal actually no nevermind the rows can be equal that's fine actually now if we have more than like n is greater if i got one so ello um we do minus one because we don't care about the final state how'd this work so like the number of rows is equal to this magic function called built-in pop count of mask and what this does is it simply just counts and counts the number of set bits okay it could be long long doesn't matter but the point is it counts the number of set bits then if n rows is great if if n rows is equal to 1 no way if n rows is greater than 1 no sorry if n rows is equal to 1 and therefore i should be equal to j or i is not equal to j then we continue otherwise if so then like we have multiple rows but some row is both the first and the last and that doesn't make sense so then um also like this row must have been a previous row that we already took otherwise it doesn't make sense and the way to do that is to check essentially we can check if some bit is set in this mask by asking is the mask here let me illustrate this say we have this mask like so then we start off with this one then say we're interested in this bit which is like two from the which is like two from the right kind of then we shift this bit over by two so we end up with this number one zero zero this is called a bit shift and then we ask is the bitwise and of these two numbers greater than zero if so then that means this bit is set in this one and this one and it's automatically set in this one so it basically just finds out if this bit is set in the number so that's how we check if something's in the mask so if masked bitwise and 2 to the i then and we check the same for j because like the rows we say are the first and last have to be valid rows otherwise nothing makes sense so now we know we have a valid state i think there may be more things to check i'm not sure and then now new row let's just say k is the new row then we have to check if this bit is not set mask and 1 2 to the k because we can't take a row that we've already taken so the current cost is cost one of mask all right new state is equal to mask bitwise or to the k because now if this bit is not set then it will set this bit by doing bitwise or set this bit by doing bitwise or then this value is cost 1 of not the math that doesn't make sense it's the cost of the previous row which is j and the new row which is k then um cost equals min would be dp mask i j v am i going to mit that's a good question i will find that out later i suppose the cost is the minimum of dp mask i j and v all right so now the new state is dp of new state the first row is still i but the most recent row is now k equals the maximum of dp new state i k and the current state or just cost action just like look at this man we have a streak of nine brackets right now oh my god um okay so now we essentially um we essentially consider all the possibilities of the first and last and um ants equals max ants and the minimum of the dp of this should be 2 to the n minus 1 because this is like it's the state where all of the rows have been used it's the full bit mask essentially where everything is a one um and then this would be um i j and the cost two between i and j now and also let's see so mask is it worth having zero be like a thing does this work if i do that like dp of zero i guess i should make it so like dp of zero having no bit set is kind of annoying so let's do it otherwise equals zero is less than n i plus plus dp of 2 to the i um where i is the first row and the last row is equal to 2 that should work i'm doing push dp here so i exclude the last state like i'm pushing this state out to new state so i exclude the last state because there's nothing to push it out to and having dp with like no bits set is kind of annoying to handle transitions for so i just explicitly like ignore that you're not printing answer i don't even print answer nice there's no way this works first try so i will try with optimism but who knows five zero three it's possible it's possible who knows i don't really care about wrong answers so uh we'll try it how much do i practice ios style tests um not that much i used to do like a ton of usago and try and like grind through all platinum then i sort of gave up on that but i did a lot of oh i practiced before now i sort of don't okay it's getting past tests that's scary all right i guess i'm wrong fine i'm wrong it worked first try my bad this is going very smoothly i think part of it is because i'm being so elaborate and explaining what i'm doing like this is sort of like the rubber duck debugging effect if you explain what you're doing and you like say it out loud and it doesn't make sense then you'll realize that i guess that's how it would work was this the other 2000 i suppose it would be i open an incognito so it like shows the tags now come on to open the original problem and then from there i can do that uh is this going up for ad-hoc attacks maybe bronze i'm not sure it's kind of like changed recently yusuko silver has gotten a lot of like ad hoc style stuff yeah this is 2000 but it's also a div 3 so who knows i am not in college i'm in my last year of high school i feel like you could argue useful is enough for ad hoc but i mean you can also like go for variety stuff like at coder and stuff yeah uco is definitely shifting you're given array a with an elements each element of a is either zero and one let's denote the longest the length of the longest subsegment of consecutive elements in a consisting of only numbers one is f a you can change no more than k zeros to ones to maximize f of a first line contains two integers n and k number of elements in a and the parameter k second line contains an array of zeros and ones so you could do this with two pointers but that's not the point of this so let's not do that let's do the dp way and is there a dpy that's a question not entirely sure if there is a dpy well you have to print the value oh come on seriously what is with this uh i have to figure out how to solve this with dp somehow and we have to print the values how fun is that why why would you want to why would you have to print the values here this doesn't even make sense uh bitmostdp is kind of hard to understand i agree there's it's probably better to like learn it explicitly first although yeah i mean it's kind of like it's kind of satisfying to solve those kinds of problems that's my opinion but it doesn't come up that often so it's not that big of a priority but i mean you could try the problem it's more up to you whether you want to or not how do i model this as a vp problem all right well this is problem oh this is the final problem final problem on the mashup probably final problem of the day i should go soon so i couldn't get the custom request this took longer than i thought it would but perhaps in a future topic stream we can do more sir i'm genuinely struggling to solve this with dynamic programming so this is problem o and you have a line of zeros and ones let's say you got like 100 101 and some like so essentially you can like pick two you can yes the number k like for example k equals two and you can pick two zeros and then change them to one so you can say like this is one and this is one and then you're interested in the longest like streak of ones you can have so the longest group of ones that's like all together and that's the idea um and i guess the way we have modeled this is kind of the same as the other dp problems now the other dp problems of like the similar like streak of ones like this isn't even dp it's like more two-pointed but say um say you fix some ending position like for example i then f of i is the longest streak ending at i what age did i learn to program seemed like i started python in middle school but it was like not that well established so i would say like the the sea pulse plus type of thing that i actually know came from learning java and that was in freshman year in high school so that was like 14 or 15 or so i'm not fast i sucked at learning python like i was terrible at python for the first two or three years i am 17 now f of i is longest streak of ones ending at it all right okay i honestly have no idea how to justify this as dp could i just call this two pointers and call it a day like i don't do you have any dp ideas chat i don't know how to do this i guess you can model it like this actually you can model it like um f i is like start position of longer streak of ones and you can observe that if you move from i to i plus one and let's say the starting position is here then like i didn't re-pin the thing oh whoops that is a mistake thank you for noticing that so like the basic idea is if this is the best you can do then if you move over here then you're gonna have like more zeros so there's no way you can do better and move over here when you have more zeros to deal with so which means like as this goes right this is also going to go right so the idea is that f of i is less than or equal to f of i plus one yeah you could binary search too that would work um binary search two pointers any sort of thing oh wait that would make sense okay if you do binary search with prefix sums that would be dp i guess because prefix sums themselves or dp all right i'm not gonna do that the two pointers is so much nicer but okay the way to do dp is to like do the prefix sums like let p of i be number of zeros on the values one to i and then like like the count of zeros on some range l and r is equal to p of r minus p of l minus one and so this is dp because p of i is equal to um it is dp what do you mean it's this dps fibonacci is and everyone uses fibonacci as dp it's the boolean condition of ai equals zero which means that this is one if true and zero if not plus p of i minus one it's definitely dp look it literally relies on previous values man that's that's what dp is i mean if you really want you can do it in like uh some weird kind of like stuff that goes on but like p of i relies on p of i minus one even though the tree is like not a tree it's like even though the recursion tree is not a tree it still kind of like makes sense and i mean if you want to make it dp you could do the standard trick of converting the parentheses to brackets like p bracket i and then now you're working with an array and then it's definitely dp depends on how you implement it actually but anyway that's that's probably why they tagged it dp i'm trying to justify why they tagged this problem as dp but the basic idea is now say you have some starting point and you have some array like after this for example then you're interested in the condition like what's the longest subarray that has um less than or equal to k zeros starting from here all right i guess i can do this you're second to it like this why not so we're interested in the longest subway that has less than equal to k zeros but like when we get a longer sub array like the number of zeros is only going to increase so therefore if we have some subarray that has more than k zeros then every longer subarray is going to also have more than k zeros and if we get fewer elements then we're always gonna have fewer zeros so if this sub array has fewer than k zeros then any like sub sub array of that is going to also have fewer than k zeros which means that like there's if you consider like the ranges where it works like all of these are valid up to a certain point and then it like stop and then it starts being bad and then it starts being bad off until infinity so you can binary search on this point where it's the largest point that still works that's the idea yeah i forgot to pin it before all right but basically the idea is you can binary search from each starting point okay i guess i can implement that because that's to finish off the dp sort of style that's what i should do i guess why not so we can do binary search um and then i can also stick that in the stream um for like zero i'm not doing two pointers i'm gonna drop the two pointers part and do it explicitly dp just to be annoying um length comma start because we have to construct the answer so we need to know the starting position that's the best for us okay it's not exactly a dp solution the dp part is computing these things called prefix sums where basically we're looking for the sum of zeros on a range we're looking for the number of zeros on the range and if we can find the number of zeros on a range then we can binary search on the largest range that has at most k zeros so the way we can compute this is by we compute the number of zeros on like every prefix like for example we compute it from on the first one element then the first two elements um then the first three elements then the first four elements and so on random colors here right and then say we want like the range two to five then like this is one this is two this is three this is four this is 5 this is 6. so we're interested in this prefix but then we sort of have this excess so what we want to do is we want to subtract out everything that we don't want and essentially that means we can subtract out so currently we have one to five so if we subtract the interval one to one then we end up with the interval two to five so essentially we subtract this out so we cross this out and then we get exactly the interval we want but the point is this sort of prefix something where we compute the prefix that's the dp part because the prefix sum is simply the previous prefix plus whatever the current element is that's what that is and then from there we do the binary search um and that's fine dpxy max length contiguous ones with y zeros in between them uh [Music] i want that like bn squared it's like a lot i mean yeah okay that's another valid solution that works but for the constraints it doesn't i assume people tagged it because there's an actual solution with it like you can say everything is brute force but you can't submit brute force to everything and have it work you can say everything is fft you can model the you can model integer multiplication as f of t and that would work but like nobody does that so don't and then i think you can do like i mean okay yeah it's stupid like dumb things that aren't worth thinking about so let's do the prefix sums now because that is worth thinking about we have at most three times ten to the fifth so proof zero equals zero brief i plus one equals proof i plus the boolean condition of a i is equal to zero this will be specifically one if it's zero or not if not and this is equivalent to also saying not ai and bitwise magic but this is just asking is it zero or not if so add one otherwise not um next idea is to simply cut a beginner contest i'm not sure i might twitch it actually i'm not sure i kind of don't have more time this week because next weekend is going to be um next weekend is going to be busy there's like round 6 85 um on the weekend and then after that there's one on code chef that i'm doing on sunday so kind of just like i don't have much time to do things and that's usually the reason why i skip contests either because of school or because there's just other stuff going on that makes it impossible so in short probably not unfortunately what's it doing right right fix the starting point then l equals i r equals n if let's see so um let's do like get sum or something l l r return brief r plus one minus pre l this will give us the number of zeros if get some lm is greater than k r equals let's see let's think about this binary search here so we query this point middle if this is too many then we have to go into this range and therefore we cross this whole thing out so this is too many then r equals m else l equals m plus one that's how it works yeah r is exclusive so then um best equals max best make pair um what would it be so be r minus i and then i we store the length and the index so then um wait co desktop first endo equals zero minus less than n i plus plus then the range we have is the range of best dot second the beginning and then best dot second plus best stop first is the range this side is exclusive this site is inclusive the other is exclusive um and then we ask if it's within the range um best s is less than or equal to i and i is less than des dot s plus best dot first see how one else cl ai that's what we want right and we say we get five somehow let me get five how does this happen also there's a separate way to handle binary search like this like you you pick the range and then you ask about the middle and basically what you consider is you consider like the final position where l plus one is equal to r and therefore like if this is valid then you're going to jump to this one and if not then you're going to jump to this one and so like you can sort of figure out the whole way to structure the binary search in the indexing based on only considering the last thing you're going to do but anyway that's a that's a topic for something else like this isn't that big a deal you just um do it like if this is valid it's gonna go okay but why should it be minus one i suppose r is exclusive why does that work whereas are not exclusive no it still doesn't work okay what what have i done as i get this seven why does two get to seven i have no idea what the easy binary searches also um why does two get to seven i'm doing the perfect sums wrong somehow do okay this side that way don't understand what how's the range on six to seven negative one what exactly is it doing okay that shouldn't be a problem like what is what is two to five two to five is two i might get sum is assuming zero based indexes but that like uses the one based prefix sums i don't know i'm doing some sort of indexing wrong like reading the values no it's not r equals n minus 1. my binary search is exclusive of r like the current range we're solving for is inclusive of l exclusive r parallel best right then prefix of zero is zero does it mess up the other one what is it doing it does mess up that one too take off by one or something i don't know why that is annoying so somehow three gets ten okay i guess we're going to trace this because i love that why not oh that's why it should be in m not l m yeah whoops otherwise that would make things too small what the hell did i go okay there we go yeah okay that's a bit annoying all right well that is this whole mashup done in like okay the problem was that the problem was that what i want to do with this binary search is i want to figure out what's the longest like prefix of this sort of sub array starting at i or what's the longest sub array starting at i that's um that has fewer that has the most k zeros but the problem was when i was modifying l i was also changing the starting point so what i had to do was make this i which is fixed instead of l which could change okay and again the dp part was doing this prefix some sort of thing if you uh miss that you can rewind or something all right well that's this whole mashup i don't have the energy to do anything else but um that is that i suppose what else did i get wrong oh right it was that like that thing that annoying sorting all right yeah this will conclude the stream i hope you enjoyed if you missed some of it this vod will be up like later so it should be fine i'll put timestamps and stuff uh it'll be great all right i enjoy life i'll see you all

Channel: Colin Galen

Views: 49,157

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: kCY8seazgFU

Length: 209min 56sec (12596 seconds)

Published: Wed Nov 18 2020