Codeforces Round 667 (Div. 3) Stream + All Solutions (A-F) (+ extra)

um all right i guess this is working um hopefully you can hear me can you hear me say something in chat if you can hear me so i don't know how this works okay i'm gonna assume that's a yes okay cool i'm gonna update the post then and then we'll get into things okay let's see okay so i'm going to can i do this virtually what's happening here why is this not um it should be like set up so i can do a virtual maybe it's not gonna work that would be funny yes please don't tell me solutions i'm going to be doing this like a normal contest so what i'm going to do is i'm going to open chat on my phone and then i can see um questions it's gonna be my setup [Music] um hey i see there we go loaded now so we'll set it up yeah we're good we're going on the virtual um let's get all my files ready just a bunch of macros okay it does have system tests it will like it will just re-run them on the hacks not specifically system tests how was school um uninteresting basically as always i want to just copy this and then never respond to it no i i respect my teachers come on besides they have attendance and stuff they have ways to make sure we actually are there 12 45 uh yeah it looks right so we'll start in three minutes i'll give you the rant about face reveals later um later during something probably during the contest i guess or while i'm going so this is my first time doing something like this i have no idea how this is going to go yeah i put that in the description right there should be how do i go here okay echo um yeah here join this and then you can find out when streams are gonna happen no i'm not actually i'll give you mod um then you're gonna get i guess click the dots but what are you banning for what i'm starting in this much time so two minutes yeah but who are you gonna ban that's a bit scary okay all right two minutes left get rank 69 yeah i can try something like sexual do anything i'm not sure there were some videos like thinking about how the youtube algorithm works i don't think likes actually do stuff uh how am i doing i'm doing great uh this is exciting should be fun hopefully happy to do this yeah yeah my camera isn't working i agree it's not working and it won't work for a while oh shoot thank you i should update the template right i forgot about that it's been a while actually i haven't done a contest in a while so this is um 1101 and we'll put that in perfect yeah thank you for reminding me okay 30 seconds let's get started let's get this set up ready don't know which order to have tabs in obs is doing what it wants so let that happen no i'm not clicking that message oh we start okay i'm gonna open all the problems so we have a yet another two interest problem so first um what i usually do with kind of easier problems as i read the input as you go as i go just so um i don't know so i can read and code concurrently so right now i'm reading in the test cases i'm just reading in the numbers nothing big so in one move you can choose some integer k from 1 to 10 and add it or subtract it from a you may use different values of k in different moves your task is to find the minimum number of moves required to obtain b from a okay so here's how this works you start with some number five then i'm not fixing my camera i'm gonna leave it broken so you start from five then in one move you can add any number in the range negative ten to ten because it's negative ten to negative one uh sorry yeah negative 10 to negative 1 and negative 10 to or positive 1 to positive 10. so after one move basically you can get to any number within the range so this is a then you can get to a minus 10 and a plus 10. then after two moves you can get to any number in the range a plus 20 and a minus 20. so now we're interested in the number of moves we it takes to basically encompass wherever b is let's say it's over here at a plus 25 then after three moves we'll have it so basically asking how many times do we have to add 10 until we get to a number greater than or equal to b and this is the answer to this is um the ceiling of b over 10. so that's what we do i think uh maybe i misread it in which case that'll be sad so first we compute the difference which is basically the distance between a minus b and we want to do the absolute distance because it doesn't matter if we go up or down then we just print the ceiling of diff over 10 which is let me test on the sample then i'll explain why that specific formula works okay so submit that and then i'll just quickly show you why what i'm doing for ceiling is um because c plus division is automatically floor it's basically i'm doing floor of b plus 9 over 10. and the reason that works is consider the value b mod 10 which is basically this will be 0 if it's divisible by 10 and some other number otherwise so if b is if b is equal to zero then we get exactly um b over 10 because no wait um let's call this c and then we say if c is equal to zero then we get exactly b mod b divided by ten because b is divisible by ten so the ceiling shouldn't do anything but now if we say c is greater than zero then notice that this is always going to add something essentially if c is greater than zero then this will be like it'll be some number it'll be some number that's divisible by 10 plus some number that's greater than zero so if we combine these two then this is going to add one to the answer so basically we get this and this is essentially equivalent to ceiling and that's why that works um i don't know left up kind of vague i'm not really sure if that's good so we got a let's do b we're intentionally going kind of slow which is fine i'm sure my rank isn't going to be too great but that's okay because that's not what it's about b minus one over ten plus one yeah that works too uh whatever you want to do really okay um more test cases so you're given four numbers so let's read them in yeah i mean there are a lot of ways you can implement ceiling it doesn't really matter what you do as long as it just works so let's see how's the stream doing we're doing good what did i do i had the chat open on my phone and then i lost it one second okay um yeah anyway so choose either a or b so you can do n operations choose either a or b and decrease it by one however as a result of this operation value of a cannot become less than x and value b cannot become less than y okay so let's get a bit of intuition behind this problem [Music] um let's think about two numbers that sum to 10. um we're going to multiply two numbers to sum to ten let's take one times nine and now let's take for example two times eight we're just going to list all these out actually just to get a tiny bit of intuition this is a 6. so 1 times 9 equals 9. 2 times 8 equals 16. 3 times 7 equals 21 4 times 6 is 24 5 times this ham writing is amazing 5 jesus yeah 5 times 5 is 25 so this is simple then we're going to you see that if one number is if like the more unbalanced the numbers are the lower the overall product is and we want to minimize the product so like if the numbers are more balanced and they're closer to each other then we get a worse product so what we actually want to do is um we want to decrease the smaller number as much as we can however this that would be how we do a normal problem however um like that's not exactly perfect because sometimes like we have the constraint of x and y so we don't necessarily want to decrease the smaller number um do d or e first i mean okay these few problems should take like a couple minutes each except for explanation so i don't think it's that big a deal all right so the way the way we're going to solve this is basically we do some number of operations to a and some number operate some number of operations to b and because of this kind of intuition it's going to be true that we want to first decrease as much as we can from a and then decrease as much as we can from b or the other way around where we decrease first as much we can from b and we decrease then as much as we can from a so let's just do both let's first decrease everything we can from a um if a equals a minus x if b b minus y and then also we read in n so then worst equals 2 e 18. just some enormous number that can never appear so first we find out how much we can decrease from a which is the minimum of the amount of operations we can make in n um then actually here let's do this this is kind of a cool trick where basically we solve the problem twice and we basically just the second time we're going to swap a and b and x and y and then therefore we basically we basically switch a and b but it's like doing everything on b at the same time that doesn't make sense um let me just show you what i'm doing so at the end of this loop we're going to swap a and b and then we're going to swap x and y so it's basically like saying instead of first decreasing from a and then decreasing from b and then later we try decreasing from b and then decreasing from a for implementation details we're just going to decrease from a and decrease from b and then swap the two positionally and then run the exact same code so we don't have to over complicate it yes the guy in blue is definitely a bot i will have to ban him someday so now the minimum here is diff b and the number of operations we have left to make then worst equals min worst that's just a minus the number we decrease times the number would decrease but it's actually best not worse because this is yeah uh right parenthesis parens see if that works that looks wrong okay what's with that that misread or something oh wait now okay i miss somehow oh we have it wrong okay that's fine um why do we have that wrong also why is it overflowing this is fun what's going on here why is this negative what is this okay so we're gonna do that do that a can go up to x b can go up to y okay this is debugging skills right here so what's happening oh my god this should be two but that doesn't even make a difference but it does it shouldn't doesn't okay fine so let's i just realized that we need to do this also maybe that'll be that does fix it okay so seven seven seven one seven seven one seven seven nine nines nine zeros nine nines fifty five ten perfect so we're ready um i'm gonna get ac this is like simple problems i'm jinxing myself right now but i hope i get ac okay have i missed any questions or hi aaron how you doing um the stream will probably last at least until this contest i might do some extra stuff and i might try hacking or something however that works that could be fun although kind of not so why do i have to do enough i'll get to it later we plan to do the whole contest i'm doing good sad you're doing bad if i hack someone it'll be added to system test so it doesn't matter if you get hacked or not either a fail system test or you'll get hacked if you're able to be hacked the best thing to do is to not be able to be hacked and then you'll be happy but you know that's not exactly always easy to do wait you were doing the contest live why why yeah hack the bot um hang on so i just how do i do this i just um click this button and then i think that works this is what i do what do i have to do guys i could do this too i guess um or that a lot of these work actually there are many things i can do to get rid of the bot okay anyway let's get back to the problem so you have a secret array you don't know anything about it and you have to restore it you know some facts that the array consists of n distinct positive integers here it contains two elements x and y if you sort the array in increasing order differences between all adjacent consecutive elements are equal upon among all possible arrays that satisfy the given conditions we ask you to restore one which has the minimum possible maximum element okay so this um distinct which means all differences has to be zero so um i guess i guess we can like the key point is here here is that x and y are small so because x and y are less than 50 y minus x is also less than or equal to 50. so that means um actually 49 but it doesn't matter yeah aaron is a gm he's just in disguise honestly it's kind of sad that he doesn't have it yet but he is definitely definitely definitely a gm i think a lot of people hear gm's in disguise action aaron orr's yeah every rule is also gm that's a thing okay anyway so we have to we so like that means the maximum distance we ever have is going to be at most 50. so let's um basically we can just brute force all distances um wait this should be y okay now once we fix a difference what do we do let's say like we have x all right let's say we have the array a comma a plus three so d equals three comma a plus six etc now once we fix the once we fix the starting element we can once we fix the starting element let's say we start at 7 then everything else is simple we just have 10 13 16 and we just need to check if x and y are in these so let's how do we do that let's say x is 10 and y is 16 conveniently then we want to start at the minimum place where we want y to be as early as possible we want we also want x to be as early as possible wait no wait we want y to be as late as possible sorry um vote to kick bot should i make more mods so you guys can screw with each other i'm gonna make aaron a mod okay what else um hey two are troublemakers so how do we do this yeah i know x and y are given but we have to like fix things i mean we have to figure out how to verify that a certain distance works and then we have to figure out the minimum um okay so there's a bit of pruning we can do here but it doesn't really matter kind of think about the details here so let's initially let's say we put y at the end then if we have length n then the first element is going to be y times um y minus d times n minus 1. either this is greater than zero in which case perfect or it's not if it's not then we have to shift the array a certain number of elements so that this becomes greater than zero and how do we do that so it's an issue i start to be um we're gonna we're gonna have the answer as a pair of um let's see max and then d order of elements doesn't matter it's not a big deal though wait is there slow mode why is there some stop spamming this is not what i intended here you guys are so annoying yeah aaron can you like ban these guys just like get rid of them i hate them they are um they they cause me trouble in my life a lot don't actually ban them but um actually up to you honestly anyway anyway anyway so this the star is y minus um y minus m minus 1 so first if x mod d is equal to y mod d then we can do it and the reason for this is because like because we jump by d that means we're only ever going to visit like things that are on the like the value mod d is never going to change so 7 mod 3 is going to be 1 10 mod 3 is 1 etc so we're only going to visit numbers that are um 1 mod mod 3. so if x and y are both the same mod 3 which they are then we can make the sequence otherwise we're not allowed to i think putting timeout just means um i'm not sure actually also you don't have to worry about missing this because i'm going to do everything after i mean i'll upload the footage after so x d is equal to y mod d then if start is less than zero how does this work [Applause] um let's do this let's make this a function because we're going to have to refer to it later so if start is less than zero s equals get start d if star is less than zero then we're going to you know we might as well re-force it because this is small constraints honestly like there there's some math you can do here but it doesn't really matter because this is at most m minus one away from zero and we're doing o of n things anyway so it doesn't matter this is some implementation tricks don't make it over complicated now if um hello then the last element is start plus it's the same argument as this being y minus that it's going to be that so if s if x is between s and e then same thing for y s equals uh what would it be min ants also my indenting screwed up that's equals min ants make pair of end and d so then we print the final answer which is okay and that will let us do this how many compilation errors do we get um s and we forgot a prince again let's not do that okay i have no idea this is right so 1 4 8 20 26 uh 10 149 okay i think we're good they just randomly shuffled the input because i don't know they're weird nice okay what's with that i guess there's some edge case or something let's try the biggest yeah reds get wrong answers too what do you know let's try the um biggest edge case we can think of so 150 50. oh that's wrong okay that's wrong wait oh x is not equal to y one point one hundred ten fifty oh shoot the element has to be one whoops um okay my bad that might be it um 110 50. okay i think that's let's check the samples again that could be it that is also stupid if it is it and it was it okay we're on the d so yeah read the constraints guys more more life lessons here the hell 162 that's a very weird constraint maybe it means something and in fact it is 18 times 9 right so that's so 10 to the 18th i see um yeah my mistake there was that the array has to start the elements have to be one not zero you can't have zero so don't do that all right what do we do here so we want to find the minimum number of moves we need to perform in order to make the sum of digits of n be less than or equal to s i hope this isn't digit dp i'm very sad i would be very sad if it was it would be very very sad if it was um yeah i don't store my code because like it i can go here and then i can just like load it so it doesn't really matter because it's all on code forces anyway okay middle number of moves you need to perform in order to make the sum of digits of n be less than or equal to s i say it's not digitizing i have uh there have been some pretty annoying um like div 3ds or e's that i've come across i am barely red that is the answer also there are a lot of test cases so i'm assuming digit dp wouldn't really pass anyway it's like 19 times 162 times 20 000 with wait two seconds now i'm not using the web app that's like bad ms real ms paint is better um not actually sure where to go with this yet so i'm thinking about like a suffix of zeros because like let's let's think about some number and let's say we have like two one three seven five that now let's say this is too high um if this whole number is too high i'm not going to specify what d is because i'm not going to specify what s is because it doesn't actually matter let's just say this whole number is too high then once we increase this it's only going to get higher until this becomes zero eventually and once this becomes zero this is going to become eight but it means we might reduce some number of things so now maybe this is too high in this case in any number from zero to nine we already know that this is too high because with zero it's too high so we have to increase this to nine but that just makes it higher so the next step we can try to minimize our numbers is make this whole suffix zero and then we make this four so now um okay this is getting very messy very quickly so let's say we have this now we have 21400 write code on paper yeah i can do that you can use um java.util.scanner and then load the image okay so now if this is too high then we have to keep increasing and at any point whenever this is enough we're fine but basically either at some point we have enough or we have to make this zero and then because we already know that this doesn't work any number of these is also not going to work because it's strictly greater than the sum of zeros so every time for every character we have to make a new thing um we have to make another like suffix of we have to add another zero to the suffix and if this is still too high then now we have to make this a three and then this becomes zero and then if even this is too high then we just add a one at the end so basically what we do is we try every suffix of zeros so for example two one three seven five so we first imagine we make all of this zero and then we increase this by one then we make all of this zero then we increase this by one then we make all of this zero then we increase this by one then we make all of this zero then we increase this by one and then finally we make the whole thing zero and um this is an edge case i think i'm not actually sure so let's test it out so we're going to make a function sum of digits i'm just going to sum up all the digits and i just do that return s now actually how does this work so hello r equals one this is the current power of ten we're at so for example we're going to try making this whole thing zero so if s dig and it's less than or equal to s then just be done otherwise we try some new stuff let's move this down here for consistency then while the sum of digits is greater than n um okay so we do r times equals 10 and divided by equal to 10 and then plus plus n what this does is essentially we're going to two one three seven five again in in the implementation wise we're just going to cut off this whole part and then we're gonna say this is two one three seven times ten but then we have to increment this so we make this 8. and that's how that works so then our final answer is going to be the current number we have say 2138 times the power of 10 we're at and um and then we need the original value of n which is the number of times we increment i think it should work uh compiler maybe yeah because i violated my own convention what yeah you don't actually see me not for a while i don't think what the hell is this like stl or something what is this why is this so long okay wait is this just the thing no what what is causing this oh this just goes on forever okay error no match for what the hell is this no match for operators oh shoot oh shoot forgot my own template yeah this is a string so it's trying to match that whoops kind of the the faults of prudent templates okay um yeah that works so we handled the edge case of having to make this one and that's it i think we're good relatively simple implementation if you just think about a bit and however the idea might be hard to get in the implementation and of course this could be wrong and i can eat my own words in a few seconds okay where are we at um even with this terrible speed i'm not doing terribly okay i have been um doing programming for 20 months by the way it doesn't it might not take that long to become red if you do practice right but you do have to practice that is part of it how are we doing here okay so let's continue we still have test cases surprisingly um still have test cases let me get rid of this now onto e this this statement looks scary so there are n points on a plane i have points coordinates whatever you have two horizontal platforms so horizontal line segments i guess um is there anything i should answer in chat or is this just chat okay i'm not gonna lie it's kind of hard to focus on both yeah uh i will automatically upload the stream as youtube i think that should i have it set to not make it private so i think it should just work hopefully not exactly not actually sure if that's how it works or not but i don't know it should you guys know if that happens actually i know other youtubers just have like streamed x minutes ago or something and that's eventually just what happens so i guess that'll be what it is anyway you have end points two horizontal platforms both of length okay each platform can be placed anywhere but it should be placed horizontally and have okay cool glad that works thank you horizontally and have integer borders if the left border platform is x y and the right is x plus k y and all points belong to the platform okay so it's a horizontal line segment note that platforms can share common points and it's not necessary to place both platforms on the same y coordinate when you place both platforms all points start falling down decreasing their y coordinates point collides with some platform at some moment the point stops and is saved points which never collide with any platform are lost your task is to find the maximum number of points you can save if you place both platforms optimally so i guess y coordinates doesn't matter where can you put the platforms uh no i don't really have a math background i actually kind of avoided math because i hated it okay so i'm pretty sure the y coordinates don't matter at all unless i've misread something because they're just going to fall and as long as you have the platforms at some like negative y where it's going to catch all points as long as they're at the similar x coordinate then that's fine okay so now we're going to do is we're going to read in the uh the one reading the input what else are we reading yes c into n and decay then um read in the first array and then because y doesn't matter we're just going to not use it okay perfect that's okay it wasn't a hint i'd already um guessed that so it's fine nine out of ten what do you want what do you want it to be fine um let me find something let me find something weird i can make this i wonder if this will compile okay we're going to read into pie i see this compiles damn okay that's sad i guess we need to do that discrimination against the y-axis well it's useless what do you want me to call it yeah i can't read into pi so i guess it'll be um sad anyway anyway anyway come on let's focus so we're gonna sort because we might as well so the basic idea is um so why does it matter so you basically have a bunch of points on a 1d line let's say this and you can always show that any optimal platform is going to start on a point because um that's kind of just how it works like let's say let's say there was a platform that didn't wait actually is that true yeah it's gonna either start or end on a point i'm pretty sure because let's say it didn't right then you can just like either move it here then you can just either move it to start here or move it to end here or move it to start here and because i can't draw lines and because um like we don't hurt ourselves by moving it over because if we move it to the nearest point to the left then we're not going to lose any points and if we end up losing a point on the right then we can instead move it to the nearest point on the right and then we can't lose a point on the left um there's some mathematical basis behind this that makes it work like say here i'll just um give more intuition on why this is true so say there's some like say you have some points here and here then there's some distance x uh i'm not using these coordinates these are just random variable names actually i'll call these a and b so there's some distance a and some distance b and this is the distance from the nearest point to the end on that and the distance here so if a is less than b or a is less than or equal to b we can shift this over to the right a units and then it's going to it's going the uh platform is going to end here or start here and then actually it doesn't matter really what happens um yeah actually we can either okay wait so this i kind of over complicated the proof actually it's even simpler so either we can like shift it over to the left a units and then it will start here or we can shift it over to the right a units and it will start here and because there's no point in this region or this region it doesn't matter like that we shift it so we can always end or start at some point now what we're gonna do is we're going to um i may be over complicating this but this makes sense to me so we're going to just try all starting points and the way we can do this we're going to try all starting points and then try all ending points um let's say for example we start here then we end here then when we start here um um okay there should be something better actually when we start here then either a point stops being on the left or it starts being on the right so if we have some sort of like if we have some sort of like pointer here that says like basically everything before this pointer is is within the interval it's like left enough and we have some pointer here that says everything is within this interval then let's move this out which i'm going to make these different colors let's say we have a blue and blue pointer and a green pointer now say we move the blue pointer over here because this interval is going to be more to the right this green pointer is also only going to move to the right so for example it may move over that's not what i meant to do for example it may move over here or may move over here or maybe move over here but there's no way it can move over here because we just move the yeah i know i'm considering one segment i'm gonna i know i didn't misread that i'm going to do it later so this pointer is only going to move right and this pointer by the by definition is only going to move right 2. so the pointers in total are going to make out most n movements so in total there are two end pointer movements so the whole thing is o of n and with this pointers we can just keep track of how many points we have in the interval um yeah so okay another issue we have is that there can be multiple things at one x coordinate but what we can do is we can basically say instead of just having all the points we can say we have we have three points at this x-coordinate one point here one point here let's say we added another point then we have two points here and then it's kind of a compressed form of the thing now this isn't the whole problem the problem is we can place two platforms so what we're gonna do is this is i'm not actually sure how well known this is but this is a known trick or basically i can code less cancer or whatever i'll just figure it out you don't yeah you don't have to compress i guess i don't know i just feel like doing it because that's what i'm comfortable with so basically we're going to say this line okay first of all if platforms intersect if say we have this intersection then it can't hurt to move this platform out so we're going to assume the platforms don't actually intersect each other which is fine then what we're going to do is we're going to say let's say we fix the point let's say we fix the point where um where the segments are going to be separated then what happens is if we know the best segment we can have on this side and also the best segment we can have on this side then we just combine these and then once we try all possible separators then we have the answer so now we just need to find the best segment in a prefix and the best segment in a suffix okay so a convenient way to do that is let's say we have a prefix then we know that every segment is going to end at one of these points so we might as well just take all the possible endpoints and at the same time if we're solving for this suffix every segment is going to start at one of these points so we might as well have it start there um yeah that should work okay yeah that can be true sometimes if sometimes explanations aren't good like it's better to have some sort of like intuition to it but kind of depends okay anyway we're going to do the compression because i'm lazy and the constraints are 2 times ten to the fifth so count now for this is how we do compression then um i know you can do auto i don't really care so basically we're just going to rewrite this to be instead of having three points here we're just going to say we have three points at this location and yeah also you can just be in a stream to have fun like it's not necessary to i mean get anything out of this i actually don't know why people enjoy watching these i kind of do myself it's just kind of satisfying but other people i don't know yeah fun are we still streaming we should still be streaming i have zero dropped frames so far i think that's a good thing um comp m plus plus equals x dot s wait um x just in general okay i'm doing e right now so now we're going to um let's fix this as a starting point and then we're going to sweep this starting point to the right and then we're going to do the same thing on the left we're going to fix this as a starting point then sweep the starting point over and um you like mindful okay that's weird um okay so count equals zero so our point equals zero for i is the point we're starting at so while a i dot so the first thing is the location and then the second is um this is the pairs of location and count what are these images you're sending did you just send a loading thing so while our point why did you send a loading thing well our point is less than n and let's see a our point dot first plus k no ar point is less than or equal to a i dot f plus k basically our point is going to go this is messing it so we have a starting point here our point is going to be is going to eventually be at the location where um our point is eventually going to be at the location where we're out of reach of the interval and it's going to be the earliest location when we're out of reach then whenever we move the reach and then we become in reach now we have our point here so we can add this and move it over okay so while a our point.first is less than or equal to the end of the interval then count plus equals the number of points at that x coordinate our point.second then um now we're going to use b for am i going to qualify for esco camp no so we're going to use b for best starting at i and then c for best ending at i and the code's basically going to be the same so best i no sorry i screwed it up already bi equals count and then count minus equals the number of because now once we move this over we're going now once we move this over we're going to start excluding all the points at i so we have to subtract whatever we just had here so it's count minus equals ai dot second now we do the same thing um how do you do the coding thing yes i am drawing with my mouse how do you do the coding thing um okay so the first step is um open command line and then actually knows honestly i shouldn't make this joke so never mind uh yeah let's not do that it's a dangerous game i'm playing so theoretically count should be zero by the end of this but um okay let me read chat because i think i missed some stuff how did i learn cp i kind of just taught myself like um go to usa go to train.usco.org and just start solving problems that's what i did kind of works out um i am drawing with my mouse bunch of emojis that's fine i think that's what i missed i have minecraft i don't play anymore as much i think it's this right it's like this is the command that deletes everything i was just going to say to do this although i don't remember what it actually is so it wouldn't even work yeah don't do this but this was the joke i was gonna make don't do it it's gonna like delete everything rmrf star don't do that yeah whatever you uh however you guys do it i don't actually know how bash works that well so or you can um similarly you can search delete system32 and then this is a good way to get started in programming as you won't have a computer so you'll be motivated because like if you don't have a computer you won't waste time right that is the idea behind this so if you delete all your files or delete system 32 then you're gonna be happy that's fair use right okay yeah i'm being productive right now i'm distracting myself with my i'm distracting myself with my tips on productivity so now same thing l i equals n minus 1 i is saying zero x minus um this is actually the left point which is where we're going to call it that now so while l point is greater than or equal to zero and um i dot first minus k is greater than or equal to l point this is kind of the same thing just backwards then c i equals count count minus equals what yeah i did not make camp and i will not make camp sadly emphasis on the future which will not exist on a side note i think we just got a new milestone wait what is this youtube is not receiving enough video to maintain smooth streaming what's happening there as such viewers will experience buffering why is that happening is the stream fine for you guys or is this a problem what's happening right now okay yeah we just broke k that's cool let's keep going i started 10th yeah found out from a friend's birthday party which was fun okay so youtube's uh being crazy but youtube's always crazy so i guess that's fine anyway let's make sure this is right so we start our point at n minus one then while l point is greater than or equal to zero meaning it's within the array and um basically we go backwards here so this is the end of the interval and we want to make sure we move l point to the left whenever we're inside the interval um yeah okay so now we're gonna make two more arrays basically prefix is the best um let's say we have the splitting point be here then prefix is going to be the best thing for all points that all intervals that end at these points and then say we have a split here suffix is going to be the best that start at these points so we're going to do that r equals max r then ci because we have to end at these points so we're using c so we're basically taking prefix maximums over everything and then um brief i equals r then the same thing there are many ways to do prefix maximums that's how i do it then we use bi because we have to be at the beginning of an interval now and b is for beginning which works r intense typing um that's pretty not for training until you solve the problem that's how their system works okay so now what we do is we just try all possible prefixes and suffixes let's say we have it so let's say we have this be the divider line then we want this prefix and this suffix so it's like pre prefix i and then um suffix i plus one and it's just the sum of those and we want the maximum over all of that and we print the answer let's try it very sure it's not going to compile but yeah okay what the hell is this that's a lot way way way not again not again not this stupidity how many do we have like 15 compiler or something fun oh wait because i oh my god okay so i have to make all of these comp not a my bad because it has to like actually be the array i'm using try compiling again still something else how to solve e if we have k platforms um you can do it in o of nk by doing the same trick it's kind of like dp where prefix i is the best prefix if you have used i platforms and um actually might not be nk it might be worse actually i'm not sure about that interesting yes compilation i get it you don't have to spam it's okay i make mistakes it's fine it's not a big deal yeah where is this um minus equals map and uh okay i hate my standard of coding i'm gonna make that count instead of c and t actually i'm not even sure if we can do o of n k wait do you guys know how to do it with k intervals also this is um n log n because sorting or using maps oh well it's actually close but not close enough what does that happen so we have one one two three um okay let's just do some debugging all right stand debugging trick print everything and see where you're going wrong at this rate with all these distractions i'm probably not going to get to f in time i'm not going to be able to solve f in time but i mean whatever it's not really about the virtual anyway it's just having fun doing problems whatever works okay so um first we have to let's take this and sort it manually so one one two three four five five then is this right no it is not not at all oh wait wait hang on oh so we actually want to make all of these m which is nice because we only have m points instead of n because we compressed it to have an m oh shoot okay number one but finding our place isn't going to work here all right move match whole word only then replace okay that should work six oh it's still oh why is it still oh [Music] um because there's a special case if we have exactly one coordinate and if we have exactly one coordinate then we just get everything so that's a win for us and otherwise there does exist a divider point so does that work that works right i guess actually what we can do is um we'll also max of suffix zero that is the whole array as a suffix and prefix um n minus m minus one and then basically we're going to consider using the whole array then we don't have special cases six one five ten let's try it i guess i guess i guess i guess this is definitely sketchy i wouldn't be surprised if we got wrong answer but we don't okay yeah we're doing worse our penalty is so bad it's kind of funny okay so yeah um i can go over the full solution to this because i was kind of just sketching what i was doing before all right this is e actually do you want me to hear a big decision guys do you want me to explain e at the end of the stream or right now can i do a vote on youtube i don't think that works how many problems have i solved i can um find that out right now so at um what is it what am i looking for standings and then friends only and i can find myself so i've solved 945 right now that's just on code forces okay it seems like there's like a 50 50 split between now and at the end so uh hide solve problems is an extension um specifically what is it code forces enhancer so if you just search that up and then like for example this then you can install and it'll do things for you okay you guys are saying end okay one person is spamming end all right just for that i'm gonna do it now so interesting reverse psychology if that was your plan i'm gonna be impressed but we're doing it now other platforms okay let's see we can go on code chef and then just yeah screw the fact that there's a contest right now whatever on code chef we have um 124 unique ones um doesn't have that many i'd say like it's a hundred in total there's each contest has three problems there are 12 24. let's say roughly 100 to 200 in um from musica and app coder is a small number maybe 100 and that's basically it i'm not going to count other platforms that i don't remember because i don't remember them so they probably weren't significant yeah but used to go training is small it's like actually maybe it's not small how many problems do they have it's like a hundred or something i guess so maybe maybe 250 for musica let's say that so we sum these up was it 950 ish from code forces then 124 then um 13 13 25 something like that next year next all right i forgot according 1324. i don't i don't have the exact count on accoder what i can do is um this can go to canku and then this is a nice site to use for appcoder because it tells you a lot of things okay 122. and then we're gonna plug in the account that definitely is not my alt okay so it's not my all guys so here i'll put that in chat it's like 1500 in total that is the final conclusion how did i get familiarized with advanced data structure concept as at such a low grade such as temp i told you i basically the best way to learn programming is to teach yourself it like just say you need to know something like a stack just search up what a stack is and then um programming and then just read some things and then you'll understand how it works eventually like you can read i know quora or wikipedia probably not geeks for geeks although sometimes i would not trust that site so basically just like study stuff and it'll work out for you i didn't really learn that much in school don't use gigs for geeks no bad idea there's so many articles that are just plain wrong and they yeah it's it's not a good idea oh q times log n yeah that i guess quora i don't know i don't know how corey is actually wikipedia is fine like they have some stuff no i was not mentored honestly it's not that bad to figure stuff out by yourself you just need to like oh i word this no i've not solved that you know yeah i should i should focus we have 45 minutes left i'll answer these questions after the stream i guess all right fine i'll explain to you after fine fine you got these spammers win okay you win i hate you guys but you win are you happy you should be okay we don't have test cases here that's good um okay you're given two strings s and t consisting of lowercase latin letters the length of t is two okay in one move you can choose any character of s and replace it with anything and formally you choose some iron replace s i with some character from a to z you want to do no more than k replacements in such a way that maximizes the number of occurrences of t and s as a subsequence okay so um first observation everything's small so like two hundred so n i'm gonna draw an f here just because um i don't know i should do this more often i'll just write out the problem that i'm doing in terms of paint so n k and also the number of the first character so actually well that's kind of a spoiler and n and k are less than or equal to 200. so this means um well there's greedy i don't care i'm gonna i'm gonna do it the educational way we're doing dp you know if you wanna if you wanna flex on me fine but i don't care so i mean okay the greedy would be to maybe that is simpler okay yeah don't don't give me hints come on that's not nice i guess the greedy would be to just replace everything on the ends with um the first of the second character and then you fix the number of things you do like you say you go to the end and we're going to make this an a and then an a or this an a and this is a b and this an a and this is a b all right here how about this i'll do the dp and then after that we'll try the greedy and see what happens i think actually i think the greedy should work and it's actually really simple to code but whatever yeah bad bot giving hints bad bad bot should be banned bad bot very very bad bot evil bot okay all right so let's say we built some prefix of the string like we have i'm using these as arbitrary characters not specifically these letters so let's say we have a string abcdfg right where some of them can be equal or whatever first thing we care about obviously is the length of the prefix second thing is the number of characters we've already changed and then we're going to store the number of substrings oars yep all right we're gonna um i'm just gonna draw this for the background and make that very big and make it even bigger and move to the corner okay it should be good kind of messed up the r but whatever i don't care so um we care about the length we care about the number of characters however that's not enough because let's say we built some prefix of the string then um let's say you build some previous of the string like let's say let's say t is a b then we have we have let's say um x x x can be literally anything except a x x a a a x x a x right so what happens here is this is kind of annoying because let's say we change this character to a then we get an extra a but let's say we change it to b then the number of new sub sub sequences we get sorry is just the number of a's on the prefix so if we store only the length and number of characters we can't know what we have to add to the answer so what we have to do yeah dp definitely is going to work but i think there's also some other solution maybe so we still only the length and the number of characters that's not enough we also have to store what we can add to the answer that is number of instances of the first character so we store the length we store the number of charac sorry well this isn't number of characters this is number of um operations we did it's a number of replacements so we store the length we store the number of replacements we did and we also store the number of for example a's we have so this is this is good this is enough because we don't need any more information now notice something cool all of these are less than or equal to 200 because the input is less than or equal to 200. so we can just straight up do dp with this is the state and the total complexity is something like um 200 cubed yeah don't give up unless you want to because if you hate programming like don't do it man that just sucks don't do what you hate anyway 200 with a badly drawn three and that's the complexity it's actually more like o of n cubed actually actually it is o of n cube not just of 200. so then basically we have two transitions um let's smooth this down a bit we have two transitions either we don't actually let's say either we we don't change the character so let's say we have x right now either we don't change the character we change it to a or we change it to b now actually for this implementation what i'm going to do is find n squared k but k is up to n so it doesn't matter like in the worst case it's n cubed for my convenience i'm going to assume that these are not these are not equal to each other and in fact if they're equal then greedy does work because we just want as many a's as possible it doesn't matter where they are so in fact let's code that up right now what we're gonna do is if the first character in t is equal to the second character in t then we just want as many of that character as possible so let's first let's imagine this string is a a then we're just going to count the number of a's we already have so um for let's just do that then we have five characters that aren't a's and we have some number of operations we can do let's say for example three then the number of new a's we can make is either this it's the minimum of these two because if we make more a's than the number of non-a characters we have like obviously we can't do that and if we make more a's in the number of operations we have we can't do that either so the number of total things we can make is the number of a's we already have plus the minimum of the number of a's we have left to make and the number of operations we have then we just need n choose two which is to say this this special case probably isn't necessary but i just want to like i want to make it convenient yeah didn't you see my compilers come on you saw that like what was that compiler it was like up to like hundreds of lines maybe even a thousand lines i don't know how long it was but it was insane so we want the number of ways to pick two a's and that's essentially n times n minus one over two try and work that out for yourself if you don't understand why then return otherwise now we have a problem on our hands so again we have three transitions either we don't change at all we change to a or we change to b and for this transition i'm going to assume that this isn't a or b um actually no let's not do that so we handle these transitions separately so we can only make this transition if x is not equal to a and then what happens is we basically just increment the count of first characters we have so this goes up by one the number of replacements goes up by one and obviously the length goes up by one so if we change to b then the length goes up by one the number of replacements goes up by one and the number of sub strings goes up by the number of a's and uh timestamps i guess i can do that i'm not sure if it lets me but if it does i'll definitely do that and if we don't change at all then the length goes up and nothing else unless this character is already equal to um unless this character is already equal to a or b then we have some special cases but it's not that big a deal so let's do this um 205 just some big numbers then i want the maximum yeah timestamps will be in the description um do you mean by hyperlink like on mobile i guess i could do that too that's not a big deal unless there are a lot of time stamps anyway one to yes there there may possibly be a greedy solution i'm not ruling that out i think dp is just like more um it's more educational i guess so is this is this unclear in any way like the way um the way this works so our state if you don't understand dp this may be confusing but if you do our state is the length the number of things we've replaced already and the number of the first character we have and the transitions are when we add a new character either we change it or we don't and then we just do a bit of case work to work that out okay i think that's good actually it can never be enough but that's good enough for now so while i think about f i'm going to leave that in the background i'm just going to um work out the transitions a bit here guys ask me a few questions let's just leave this on the screen for a bit i think it's necessary uh don't separate them am i excited for the div one on sunday no i'm not doing that um i have my reasons for that but i'm going to skip it and probably just make a solutions video i'm not excited for that round no or maybe all virtual we'll see what happens keep spamming every word okay we have 30 minutes left let's do this so first of all um okay so this is basically going to represent the length the number of replacements and the number of the number of instances of the first character of t we have i am too much of a cow yes i am too much of a coward look look look look look look these rounds all right like this set of authors like the uh the guys in ac every time i've gone down a rank i lost master here this was um this was authored by anton i think and then i lost master again and so goodbye where i lost master for the first time was authored by anton which is one of the the guys here why am i not allowed to see the tutorial then i lose master a second time and i close the tab somehow why does that not load okay this is authored by a bunch of ac guys or at least an anton again and then this this round wait not this one no it was that one this is kind of a rant about why i lose rating this round was like all of ac coming together to form this this bane of my existence that knocked me out of i am so i know that if i do this round i'm going to lose red like it is cowardice sure but at the same time like it's something i know is going to happen so why why bother doing it if i know it's just gonna make me lose red there's no point it's it's simple logic there's no point in doing it you guys go what i'm saying yeah i mean they're good rounds i like they have nice problems i just absolutely suck at them it's just terrible well yeah i tell you to stop caring about rating but i need rate look i've run a youtube channel and the whole principle is i'm supposed to be good at this right so if i'm not red people are going to start hating me you know what i'm saying that's probably not true but you know that's that's the idea i have being read lets me um lets me farm views that's what i'm trying to do i'll rant about facecam at the end let's let's do this for now so first we're going to fix the length we're doing push dp that means we like push we push states onto further ones like i plus one j plus one okay for example we're going to push states onto further one uh daily dose of complaining um i guess i can do complaining after the round i mean i mean either either dp works but i feel like um in terms of a problem like this where the transition is you pick some character and then you change it or you don't i feel like push dp is easier to visualize here but whatever whatever works really so first we do that then we do actually we're gonna do is um what did i just do j is less than n j plus i'm going to make some huge negative number 20 negative 29. um dpij k equals actually we're going to make this big number and then call it negative yeah aaron um knows me in real life which i think is unfortunate for him very very unfortunate almost sad even then we have to initialize the starting state so this is length this is number of replacements this is um number of instances of t 0. and remember we know that t 0 is not equal to t 1. so now first transition the new state is i plus 1 j k actually no so if so we add character of s i minecraft speedrun that's funny i don't know i'm not good at gaming it's going to be kind of sad uh the donut yes there is a significance it's a very complicated backstory that i may share in a later day but not right now do a type racer i don't know i've got like 100 words for a minute if i can focus but on stream is going to be terrible i'm going to like totally vomit so we add the character s i first transition that we don't replace so if s i is equal to t 0 then we go to dpi plus 1 j and we automatically get a new character so because it's equal to t 0 i max that and dp i j k and we just do this because we don't have any more of the answer we don't have any more substrings otherwise if si is equal to t1 then we get dpi because we don't get another the first character so dpi plus 1 jk equals max dpi plus 1 k dpi j k plus k because we have some number of again we have some number of a's here and now we automatically get another b which means we're going to add two to the answer so it's it's equal to plus k i'm going to make this an else else then we just go to dp i plus 1 jk because um like we just add something to the length and we don't affect anything else so here we get rid of the plus k and that's the transition now we do the second transition change to a or change to t zero then we get dpi plus 1 j plus 1 because we use another change and then k plus 1. so if it's already equal to a then we're going to if it's already equal to t 0 then we're going to cover it in this case so we might as well assume that it's not equal to t zero so that's fine then we just do um okay and we don't add anything to the answer otherwise the third transition change it to t1 then we have the state of the new length we make another replacement but we don't get another of the first character however we do add k again so actually this is kind of um simple because we can just copy that and it's the same transition now well the only thing that matters is that the length has to be n in the final state in the final state the number of replacements we can have can be anything and um the number of a's we can have the number of t-zeros we can have it can also be anything well actually this specifically has to be less than or equal to k but the other one doesn't matter so it's n because the length is n then we fix that and then we're done let's try it compiler wow none guys we're getting better no compilers we can get wrong answer instead four does it get anything right it gets nothing right okay what's with that must have messed something up what the hell okay okay okay okay okay all right what's up that so um let's print all the states i guess it's going to be very very annoying oh wait wait no wait um yeah we don't care about the value k until the very end so the fact that we use k in the loops doesn't actually matter i don't think um so yeah it's gonna be so messy this is how you debug yes negative is fine that's supposed to happen so 100. um no replacements no anything that's fine so 1010 wait that should be one oh oops okay that might fix it all might not who knows did someone point that out yeah yeah see ya hope you enjoyed i'm not really sure how the streaming is going it's kind of fun for me so i guess i can keep doing it three 10 16 15. all right this should be good and the complexity is still of n cubed so yeah okay that is that sure rank is quite bad because uh penalty but you know again it's not about the rank it's about solving the problems um yeah okay so you guys figure something out i'm gonna go the bathroom right now i'll be back and then we'll get this going with whatever we end up doing i'm not actually sure what we're going to end up doing but we're going to do something let me mute my mute my mic so it's kind of loud okay we're back what have i missed what do you want me what do you want to force me to do yeah what i can do right now is i can re-update the subs that should be cool let me get 1118. i missed 111. that's sad [Music] um okay let me load the chat back on mobile since i'm more used to reading that which one is that um wait 176 i'm pretty sure i did that one oh that f wait this was the i do not know how to solve that general idea is that it's some sort of dp or something where you um some sort of dp where you actually done how it works it depends on some sort of things yeah i don't know how to do that it is very hard to me at least or probably to a lot of people yeah everyone you want to get up here and explain the solution can if you want jenna's maestro i'm dominating this anyway yeah there's a lot of stuff involved in it um what is this what do these numbers mean are these viewers oh cool average watch time is five minutes how does that work there have been like there's a lot of people staying come up and leave anyway so first before we do anything we're going to um let's explain e again because that's the thing let's do e because i remember that was a bad explanation i can talk about face cam i guess okay i'm gonna leave that because that's important so let me gather my thoughts about e for a second and um make that into a wallpaper yeah why not i have an idea the fastest way i know to convert an image to um like something downloadable is this so we're going to um ors.png or just boris and we're going to make a few configurations to the youtube i hope you know where i'm getting at here how do i how do i do this channel settings i'm gonna do this it's too small what it's too small breath what am i supposed to do well i guess you're lucky what about that okay what i can try doing is move this here and then just expand it out and be very tall lettering and then i can save this whole thing and we'll go to pictures quality oars2 is this too big no it's that even that's too small okay let's make this bigger let's zoom out more and then just make it enormous and expand it this way all right now we can save that increase the resolution i don't know how to do that is there an easy way to make it bigger actually is that the way let me save what oh it's already saved okay so we got to oris ii is this big enough that doesn't work okay what do we need here we need to be 2560 times 1440. downsizes a bit times 1440. okay perfect want to use a fresh brush that would be too easy we have to extend the original overall auras what what does it want adjust the crop i just make it like not craw is that possible i don't think it's possible you might have got an accident on facebook i don't remember what's in that folder actually it might be even more interesting with the crop let's do that let's just have it be cropped yeah i can make it smaller too i guess that works let's try this you'll see it again because i have to upload it again do i have something in there yeah i do you have that i mean if you really wanted to dox me you could like hate youtube i do i hate you too okay can i um can you shift and make it scale no i can't let's try this does this work still doesn't work i will leave it cropped for now i'll just figure it out later yeah i guess i could make it smaller that's true that is that is the smartest thing to do probably actually oh shoot i left that that should work better i don't have to remember this time stamp because when everyone when anyone asks about where this came oh come on seriously seriously youtube come on how small i have to make this thing i want the oars to be as big as possible it's kind of necessary and in that picture i have my face in the donut i'm pretty sure i'm so close wait does it does it gets i swear to god okay we're gonna make it that maybe a bit more a bit less tall might be like dynamically reducing the crop as i make the photo smaller which is very very annoying okay finally uh screw mobile we're good good policy all right where are we at does it does this work now how do i go here huzzah it works took way too long okay but it works and we hit 1.12k i think i think doing this worked and made it work so that's good these time stamps are gonna be really interesting like really really interesting kind of gonna kind of excited to do them no i'm gonna explain e right now that's what i've been holding out on uh yeah so we're gonna leave this at the bottom stretch it out okay now i will actually explain e for for once also yeah i do watch chess it's kind of fun okay i'm gonna make this bigger so that it scales okay what do we have to do so in this problem we have a in this problem um one second wait someone got a photo of me or is that someone else what are you talking about oh my god no actually no no no i'm not relenting that's the only glimpse you're going to have of that image also i'm not time stamping it you're gonna have to find it um yeah i'm evil okay we're doing e right now i think do you guys want explanations any other problems or were they clear enough as i was going so we have a bunch of points on like a 2d plane and basically what we have is we have two horizontal platforms of length k so this is k and the other is also k uh you want d again that's fine anything else so at a certain point in time you're going to turn on the the grid and everything is going to fall down like so so we'll say we'll say we get a point for every no we get okay using point in both contexts is hard so we're gonna say we're going to say a point is good if it'll eventually land on a platform as it falls we want to place the platforms to maximize the number of good points that's the problem statement so the first observation is that let's say we put the platforms at like negative some like negative huge y coordinate like even below the ever world ors right so if we put the platforms below the everal auras what will happen is like no it doesn't matter where the y's are eventually they're going to fall down also below the everworld ores and they're eventually either going to hit the platform if they're within the x range or they aren't so what that means is ultimately the y-coordinate has no effect on the answer since we can always put plot we can always put the platforms below the evorable ores so now let's convert this problem to the to the 1d problem where all we care about are the x coordinates uh yeah sure liara give me mod okay jesus okay just choked on water that was smooth some asmr for you all right that was fun okay one second just gonna save that okay i'm gonna be right back and get more water because i need uh yeah i need some more water you okay this is going to be uncomfortable for a while but we're fine yeah f is basically dp dp on yeah letters number of moves and k is the number of instances of the first character you have well it might be quran i don't know i don't i think choking is just stupid not exactly um a disease i have okay let's rename the stream yeah okay now we're gonna explain e so how do we put the platforms down now that we have the 1d problem so another observation we can make is that every platform in the optimal answer it's okay to make it either start or end at a point yeah it's okay lyra this contest took me 100 minutes not at all because of the stream obviously so everything with a starter ended a point and therefore now we only have to do that so let's first say it starts at a point how do we solve for the number of points we have when it starts at a point the way it works is this let's say we're going to solve for all actually we're going to solve for all intervals that start at every single point so let's solve for the interval it starts here the interval starts here interval starts here here here etcetera yeah so say yeah two point is so say we're here then there's some point on the right where everything here is within the interval and everything outside is not within the interval so then say we move this here um why let's move this here now the end of the interval we're at changes from say here to over here let's say it's long even though it isn't long just for demonstration now this is within the interval and we want it to be outside the interval so we want to move it then this is still within the interval so we move it again and move it again until it's finally outside the interval so again all of these points are within the interval and everything else is not and therefore um exercise is not actually necessary to compress but whatever whatever whatever whatever so um yeah basically now we move this over again and then we just keep moving this over until we solve for all the points and this works because once you have this position like it's really simple to find the number of points in between it's just some function of the distance of between these two also see yeah it's not actually necessary to compress i was just being weird so what's the complexity of doing this we note that like because as we move this over to the right the end point of the interval is always also going to only move to the right and therefore this blue thing this blue pointer that marks the end is also only moving to the right so it starts here moves to the right and places and therefore it moves o of n times and obviously the first pointer also moves oven times so in total the whole thing is just o of n then wish i didn't do that so now we're going to so basically that's how we do and this is called two pointers because you have one point on the left one pointer on the right and you use the distance between the pointers to compute the answer so now we solve for all intervals that start at certain points so now we basically do the exact same thing for intervals that end at certain points except now we just um the blue pointer is on the the blue pointers on the left because we're moving the blue point to the left as we as we go on so like for example when we move this over then this blue point will move to the left and it's the same exact thing well we can work with start points i don't know like there there's probably a way less complicated implementation that you can do um actually there definitely is because i kind of over complicated it probably quite a bit but that's fine but my idea is now that you have this there's another observation you make say the intervals are overlapping um then like all of this is basically all of this is basically wasted space like it's used on both of the intervals so why don't we just like move this up why don't we just move this over so that's not overlapping right and then it's slightly better and then it's not a big deal so wait what did i accidentally delete something what happened was that me i might have accidentally messed with something on mobile no i did sorry okay so basically we show that the intervals can always not intersect except maybe at a specific point like we can draw this interval here and then the other interval can be right below it where they intersect here but they have only a zero or no intersection i don't know i might have messed something up with mobile but i don't know okay so now once we do that there has to be some splitting point because the intervals don't intersect there's some splitting point where one interval is going to start one interval will end on this side actually no it's more like both intervals one interval is going to be on one side of this and the other interval is going to be on one side of this then if we solve this for all possible splitting points then we're just done because we like basically consider every case um and this doesn't overcount because we're not going to count points twice so now all we need to do is basically let's say we have a splitting point here we want the best interval ending at these four points and then the other point is here and we want the best interval starting at these five points so that's why we do both end and start it just makes that implementation convenient and once we do this then um it's kind of just like prefix maximums either like this is the maximum all five of these but it's also the same as the maximum of this one and these four whatever they may be and then these four are the same as the maximum of this and these three and this is the maximum what what i do the maximum of what have i done indeed maximum of this and that and then that is itself so if we go backwards then basically this is the maximum of this this is the maximum of this plus this this is the maximum of this and that this is the maximum of this and that and this is the maximum of this and that and that's how you do suffixes you do the same for prefixes and then you just try all possible splitting points note that you may also want to try this this as a splitting point and this as a splitting point even if this doesn't exist it still may be necessary especially for the n equals 1 case and i guess i didn't realize during the contest that this even works even if you have multiple points of the same x coordinate which you do so yeah it's fine it works okay that's e what else did you guys want i guess um d and then i can give the rant and then we can end the stream because it is kind of getting late for many people i think let's quickly go over d actually what i can do is i'm not sure how to do it with k intervals actually that seems kind of hard harder at least we can do it with n score kdp but that's like definitely not feasible so i'm not sure for each platform you use there's some fix that that seems akin to aliens trick which is interesting unless i don't know what that is but that doesn't matter well is f um is f unclear i mean i kind of went over the whole thing as i was solving it and once you once the stream ends i'll post the live footage and then we can that'll be available it's like all the yeah it'll just be in the video later wait who asked for d are they still here did they are you d wait was my thing um was my explanation of d not clear or did you just not see it before are they still there wait what do you still want me to do it or is it okay if you just read go back in the video okay yeah i did go over d as i was explaining it so when the stream is over you can check that it might not let you go back in the stream if you haven't loaded at all because i think that might be just how youtube works i'm not sure anyway so we can talk about face cam now and there's a very simple explanation of why facecam is useless so there's three things you do in a contest right um where are we there are three things you do in the contest you read problems let's say i was solving a for example you read a problem you think about how to solve it you write the code okay these are the simple steps to solving a problem this these are exclusively the steps maybe you interleave thinking about it and writing the code and therefore you guys don't see me choking live i don't want to do that i'm not going to do that that's stupid um i don't think that increases entertainment value that's just painful so you do three things you read the problem think about the solution and write the code so how does a face cam enhance any of these like you read the problem right i'm staring at the screen that's it i'm just reading words you write the code so maybe i'm typing right i just like for whatever right then you type some code and then eventually you're done so how is that helpful like i'm writing code what's useful about that semicolon um so again i'm staring at the screen like it's it's staring at the screen and then maybe if you're thinking there either you think by staring at the screen or staring at something else or i don't know maybe pacing around do you guys want a two-hour pacing stream like i'm sure that already exists on youtube okay so emotions like what emotion is i don't have emotions like all i do is say like i say what when there's a compile error and then i say what when it gets the wrong answer and everything else so it's just like it's like yeah i got the problem but there's no enthusiasm like it's just another problem there's no there's no like beautiful emotion that happens there you guys are so annoying all right i'm still saying 10k still saying 10k i made that promise i'm going to do it 10k and we get a facecam or we get some picture or something 10k is that too ambitious uh probably is but whatever i don't care 10k or nothing yeah you have that picture i guess uh cp journey okay here this is this is my cp journey so first it starts with usico with training and i did like here right so my code chef graph is weird because i started doing things a weird ago a while ago not a weird ago um i have like i did like three contests in march and april so i'm not really i guess i can count that so cc for like one month so this was a gap of like actually that was fine and then this is a gap of like two months of just a break and then after that co-forces and that's the present that's my journey no 10k or nothing this is my journey yusuko and like a month of code chef and then go force and then there's some uh at coder thrown in the mix more code chef yes there are many people better than me in my high school aaron is an example [Music] um what else what was i going to say i was going to say something aaron is in denial as always all right what else happened it's a terrible a and redraw that i'm going to make another aorus picture i'm just going to put them side by side okay 1v1 with william lynn you guys all know how that's going to go that that is a fixed outcome that is just a fixed outcome right there there's there's no entertainment value in that video you guys want to see me get destroyed that's mean you guys are mean yes he is slightly good slightly very good william lynn probably doesn't choke on water and stream it either i can do duels maybe that could be interesting i don't know i've been trying to figure out like how um some like handicaps i don't know i've done a couple duels where i i type my code in the code forces box it's like for example my process for solving this problem would be like you write the entire program in the code forces box which means you don't get a compiler like something like this right and then um you just have to write the code and it's kind of interesting because it's like code golf where you don't have much of a template yeah i'm also done with left hand which is interesting like left hand plus submit box and then um all right and this would be how you do this would be how you solve the problem i don't have to work like this and i have slow i o so i guess that makes a difference you guys want to do duels just had like three hours of stuff what do you guys want to do i'm going to end it here actually i'm kind of tired after that i gave you my rant a chest stream i'm gonna have a variety aren't we it's not dead stream's not dead i'm just not doing anything how do i think my viewership will change after covet well it depends i don't know how um you guys lives are but i definitely won't be able to do it at this time like this is i'm doing it this because we had a half day and we had like a lot less time in school so it's good it's convenient for me i'm not sure how to work well i'm assuming people still have free time and they'll be able to watch whatever they want which may or may not include me i will be doing it after covent i don't see any reason not to i mean youtube's fun i like doing it you'll see i won't be read after covet that's the difference you see me barely hanging on the edge here right soon enough it's just going to go like whip it into paint this is how you modify a rating graph just take that and yank it out and we'll just say in the future it's going to be like actually it'll go even below the horses i think that's that's a trend for my future is my rating graph in the future it's going to be like like this i guess and then we'll just shade that in you know what i'm saying that is my plan now i'm going below the oars level that's the whole point like you see me below the horses i'm below them okay i don't have anything more um say anything else you guys want to do on stream collab with other streamers that's fine chess stream i don't know i'll think about i'll think about that yeah i usually make like regular screencasts too not just um live streams because most of the time i can do rounds live and obviously i can't stream those so like if you look at my videos there's a lot of stuff there i also have tutorials um i do have a couple tutorials just like advanced rel relatively advanced stuff like the this the um what is it i did something on central decomposition and then before have you like decomposition stuff like that collab with second thread like all the all the big cpu youtubers are like better than me that's the problem so like it'll just be a stream of me losing you guys really want that see me humiliated in front of 26 people how's he proud of me i don't even do chess change the topic to just chatting wait what decomposition um since your decomposition has no prerequisites basically you need to know what a tree is and that's it you should be able to understand everything else there's a require there's a to solve the problem you need lca however you can basically make it so you um abstract out the lca and so you don't actually have to know it you just have to know how you use it square root decomposition i mean that's kind of a different different thing though oh you want me to do mo's algorithm oh if you know if you know all that then that's yeah you're totally fine you'll be able to get it i think it's kind of hard to understand i think but flows i don't know how flows work actually ask ever will about that he's smart sure it is let me do type racer all right let's do that type racer hype you guys are ready for this let me um hang on let me pull up youtube on my comments or youtube on my mobile how do i practice i don't but i used to and i used to practice by just like there's no pattern to it you just take some random problems and like go to problem set and then sorry i am i want to do some practice right so i'll do some like easy to hard problems then i'll filter through these and you can click hide solve ones if you want you can even randomize the order kind of you can sort it however you want really uh it's taking a while but that's that's basically the point okay how do i make a link i've never actually i don't use typewriting okay join people do i give much time for school um kind of wait where's the where's the box oh i should join the race nice are you guys ready what 98 okay who's that someone is definitely flexing on me is that aaron aaron i swear to god what do you expect i'm bad at typing so many mistakes you guys are really annoying no you weren't last there's someone after you also these people that's aaron aaron is just flexing okay we're not doing that again that's painful all right at this point i have to rename this because um no no hand cam i don't even know how to do that i'm telling my monitors messed up so my mic on my laptop or my camera on my laptop is really hard to use like one time i just i moved my laptop screen back and the whole left side just snapped off of the computer so basically if i try and fold it any amount like the entirety of the the entirety of the screen is just gonna go into the monitor and it's gonna like cut into it or something so i can't i can't ever close my laptop because of that so if i tried to do something like a hand cam it just wouldn't work i wouldn't be able to do it because i can't bend my laptop like that um yeah use a separate camera that's too much work let's do that i'll answer in chat that's simple um anyone bad at chess i want somebody's bad because i'm also bad so that should be fun i'm not playing aaron don't let aaron play chess the dude's like 2000 or something let's let's start a game why not we're going to turn this into a variety stream um i have a weird name i have a good puzzle rating but that's like it nothing else is good here play with a friend time variant standard time control let's make it 10 seconds like 10 10. casual am i supposed to tell you about my alts what do you want okay whoever joins that isn't aaron can play me it's aaron i'm leaving the game are you guys able to join or does it require something no don't help them what yeah i'll play ever rule wait oh okay does that work no that doesn't work either um what does it want me to do it's my own chat come on it's not gonna let me do that okay i'm putting in the description then i have no better way to do this all right should be in the description now is it there okay who is this speak in chat so i know it's not aaron who am i playing so okay let's make a move i really don't know how to play this game like what's the perfect move here i guess attack that pawn i don't know what am i supposed to do yeah i'm good at puzzles but that's it uh okay what happened can i edit this to fix the typo no i can't what do i do here let's spend that pawn for sure i just like blocked everything but you know whatever not a big deal i won't win anyway very much hope you're not good at chess aaron stop i hate you i'm not listening to you you're mean um okay i don't care aaron um i don't know what to do i guess this why are you guys so smart what are you guys doing i don't remember what the x means but it's something what am i supposed to do here x is pronounced this takes wait so if i take that pawn then what happens here he can take with the knight and then i can take with this and then we're even i guess might open up the center i don't know and then he should take with the the knight you can check the eval bar is there one um can i do this what is painful to watch is that a blunder have i done goofed um of course black's better let's see what moves do i have here you guys are so annoying the way you're talking about this like i know what you're talking about but i don't know how to do it so you know what i'm saying okay let's castle i guess i have no better move or maybe i do have a better move i don't care aaron doesn't matter what i do going to lose i'm closing the chat i can't i can't deal with this defend that why not i hope i'm playing someone bad because i don't want to play someone good that's not fun it's not fun if we're both op or if they're op and i'm not lgm and chess yeah gonna stop overthinking things nobody expects me to be good doesn't matter i think it doesn't matter every move i do will be a blender um never gonna get that bishop out am i okay yes first time unfortunately well no not first time i guess but um i don't i don't play chess much if at all okay what's the better move here is it to open up the g file but then that like screws over my bishop so that's probably not a good idea go there was that move now okay what's the plan here um struggled a lot although it was like in total i basically put um it was 20 months into competitive programming i do i definitely know what struggling means that's not fair yes yes everywhere he is that is his name okay let's just do this i have paid in brain power and mental health um okay this is a move i have have that what have i done here um what is the response to this no i don't really have a religion i would say yeah i'm pretty sure i'm dead here or something bad something ungood because there are some scary moves ahead i currently am a student so i don't have a job stop giving him moves that is mean who plays that movie when we mad i think five minutes is too long i think shorter games are more interesting because then there are more blunders you know go in the shorter game next time he does play it that's annoying i don't want to play you aaron you're you're a problem why would you lose is not going well um this is very not going well it's going very unwell i think i've already lost here is that how that works i think i have yes i see how that works you guys are giving him the winning move i get it why are you guys cheering on you're cheering on my opponent not me yeah best move is queen to e4 isn't it then the bishop stays there whatever i don't care i don't care it's just the game really not the best move but a move at least aaron tell me was queen e4 better i know other people are how much better was queenie for nice no it doesn't do that um i'm gonna yellow it no matter what i do i'm dead anyway aaron i'm ignoring you how good is my opponent action because that seems that seems too good to to be bad oh yeah wait that does oh what am i what am i thinking yeah you're right about that that was better then at least also get some more things all right had i get it get it aaron um i hate you guys let him win whatever it's better than me that's for sure yeah sure maybe we don't find the optimal move every time but what does that matter what is that let's open this up yes i'm pretty sure that's the case for me too anyone can annihilate me um i don't really play steam i guess aaron i absolutely hate you your presence causes a disturbance i'm acting to i'm acting yeah i'm a paid actor um i don't know totally lost at this point anyway does that do it that forces me into that corner and then he does yeah okay yeah that's enough i knew it was lost but at least now i see how i lose because i mean here it's over because he'll do that he does this right here now wait i did this what did he do played that i played this he did that yeah and i took with the bishop didn't really matter and i do this he does that and he does either i move here and moves the knight there and he wins okay who i was definitely playing someone better than like someone way better than me i think maybe you guys underestimated how bad i was yeah i can't see the spectator chat i mean i can't see this was their force made earlier i think here it was fine i was losing and then i just had to do that but instead i guess i gave up that defense yeah okay sorry guys i don't look seven moves into the future that's not how i play chess well i guess this was a good move because it forces a threat what does this do oh the queen's still there oh i forgot about this queen and a bunch of other stuff wait i was winning what all right this is confusing i don't get chess clearly okay i'll be right back and drink a lot of water going to the bathroom i guess i can play a few more lose a few more i'll play everywhere how about that because you guys are crazy i'm not 1500 whatsoever okay we're gonna do some faster games um all right let's play bullet actually let's play blitz not bullet let's play three minutes i'm going to challenge you let's play some shorter time controls so three minutes and then 10 second increment still works a rapid that's what it's called okay i don't remember challenge the client what do you want then so okay let's do things you guys can still hear me right did i return on my mic okay i'm not really sure how to do this i don't know how to open um you guys bring swing the bishop out um aaron is not ever will no that's someone else interesting okay what is the plan here the plan is to lose i think well with double equals like with math it's just wrong like you you can't say like it's just not the right notation i don't think that's fair to say that okay um let's do castle's one up live on the edge uh thanks mwahahaha um go do that why not anti-chest oh yeah anti-chest is fun maybe we should do that instead ah this development is op i don't know how to attack i don't know how to do anything in this game honestly that's not a good idea go away aaron nobody needs that for me okay this is mean too lazy to move the light tonight let's just not oh actually i could have no i couldn't have done one um don't know what i'm doing anti-chest is where you try to lose all your pieces yeah let's do some antichests that's more fun i like variants more than the real game to be honest yeah because you're yeah because you're forced to take i know if i want to run down on time to keep more interesting okay let's do that then i can do this [Applause] um and then this i'm thoroughly evil oh nice and i didn't see the rook nice whoops um did not see the rook there okay so what can i do now stop suggesting moves i don't like you my goal is to try not to blunder my queen i think that's the best strategy here forgot the bishop was there um all right what i do swing the rocket it's like a kaleidoscope of bad moves i can bring this knight in it's funny to act like i have logic behind my moves i have to make i have to make faster moves nice okay so that will do something okay um that defense i do here you gotta play for nice yeah there goes that okay nice all right let's just do a thing yeah i gotta be faster i don't see that it's kind of sad yeah i know i know i know i get i get it um i know i messed up man we're all sweeping this now this is sad now i need to not flag well no because the the bishop was defending the the rook so that's not a good thing that's a nice move kind of let's get it off easy if i don't flag maybe but that is the problem isn't it yeah this is what um good time controls is for okay we trade uh oh i don't even have to i don't have to do anything okay yeah because he can't reach me nice okay okay we're doing anti-chest now we're not doing normal chests this is lame i reject all of these because i think anti-chess is more interesting actually here i have another idea what we can do is um this is interesting um there's interesting mode i'm putting it in the description there's interesting mode called horde you guys should see it for yourself whoever whoever gets into a first wins you guys see this board right here okay are you are you good i don't know okay now aaron can't make fun of me cause it doesn't know ford yeah i messed up many many big mess up how to what what do you mean mate pawns oh you just have to kill everything i have the win for black is taking away all of my pawns yeah sugimoto is a troll he is not from blair the computer says by default white is winning because like more material so there's that [Music] oh there's a very there is very many way for me to screw this up very many indeed all right aaron i get it get it every move i do is a blunder don't know how to play this game to homework nice a three-day weekend that's all you want let's see yeah we'll do anti-chess after this i'm not i'm not sure how to play this even first name is colin i reversed it for effect not a very specific effect but just an effect it'll get more interesting once i stop stalling because right now nothing's hanging i'm not actually sure what i mean just an effect like it has an effect just not much of one so up gabe playing chess because i'm out of cp things to do and aaron just left even though he's like omega troll okay i'm not gonna let you do that actually i probably will let you do that that was relatively standard um the div three ah there's a bit of interesting stuff but like not that much i guess okay i think i've lost this pretty sure i have i don't really know how to attack like this to be honest well the queen's not the worst thing i just don't know how to attack no first platform for programming was yusuko all right i'm bored yeah this is over i don't have an attack here let's do some anti-chess you guys hear the lawn mowing outside is that too loud yeah i know the goal is to um oh yeah the goal is for black is to get behind no as in it's not a problem okay that's good okay you don't have to tell me how to play anti-chess it's okay it's fine i get it these are all backseat gamers swear gabe you're still here i need you can't deal with these people um i use overleaf for for example mbit the competition we had and some other stuff too oh no gabe i just need you because they're gonna like keep me sane these people are gonna keep me unsane um yeah come to embit guys it's a good competition i i definitely do a lot definitely oh shoot that was bad because now i let him do that and bid is our competition that's what i use overly for because we write statements in law tech okay so i have to pre-move that yeah for anti-chess you have to yeah anyone can um join ambit you just have to like yeah um okay what's the best move here i'll block myself that's a good move now all you have to all you can take is the queen and to chess is indeed interesting i don't think we'll be consistent about solving like about um doing this but should be fun for a bit um okay what's the best move here i think that is good because it needs to do something [Music] what the modes are there i'm not sure interesting now i do this and if he takes the knight i go here and then i'm out of and then i'm out of captures for the rook so you can take the knight or you can take the pawn either one works um okay that's good now i can do this probably should have gone double but whatever i've been doing competitive programming for 20 months no it's not a draw what do you mean this isn't over okay um let's see what else can we do play other people in anti-chess some other backseat gamers let's do the best opening ever uh he resigned i think so i joined another one i was just doing i do not play chess no i'm not i'm just doing it because people wanted it for some reason 960 i know what that is it's like it's like the pieces are randomly permuted but i mean you still have to be like you have to know how to play moves it's not just about openings i don't know how to play moves that's also the thing the skill just isn't there not ping people i think he's dead so play someone else all right let's do this best opening you uh okay i haven't been looking at chat what have i missed yeah i know i know the rules i just don't like them um okay forcing to take that let's see i can take either this is an interesting game mode i'll move that out i guess okay okay i do multiple pre-moves that's a bad idea see and this is how you win because well you want to promote to king because the king has the least reach or king or knight all right good game this is this is a very funny match okay we'll do another anti-chess all right let's try this opening again long develop theory oh crap that's how you counted that nice um okay now he has to take i'll take i'll take my rook then i will open up the king side um okay now we're at this situation again so i guess i want to do this now what i did tight i did type race it before it didn't go well okay i'm losing this and then you can move that and what now what do i do here oh oh that's good okay now now he has to lose that rook because even if i move the king out of the way then the bishop will um have the discovered defense which is not good so i don't think there's anything i can do except for try and get my knight out guess either way okay then he loses both rooks shoot that's kind of bad yeah because now i have to take that then okay i'm almost lost that's good although not entirely shoot that's a good move and then he can move his king or his pawn he moves his king and i have to take that oh wait he moves it oh i thought it was gonna okay i win that gg that was closer that was closer that was good thank you keep doing anti-chest okay what is the optimal opening here all right force that to happen then open that up and then what take with the king take that make that happen then we'll threaten a queen loss or we'll threaten a queen sacrifice shoot that was dumb what's that okay that was not smart i'm losing this okay okay okay okay come on get your head in the game it's all for one pawn isn't it okay so he takes i have to take and he'll take i assume well probably not many people are watching because it's kind of late i can get that i think it's a better move oh shouldn't have done that okay now i lose the queen and i have to take but now it's more balanced he's actually he's up on material all right now now we're even now we're even material so my goal is to keep my rook trapped um i'm gonna do that then we'll lose the bishop then no matter what we do we have to take with the rook or we can block our rook off i guess now looks blocked off by the pawns which is interesting okay there goes the advantage better move lose the rook all right now he can oh shoot that was that was bad oh what have i done okay so now he has to take that all right we have two pieces left how do we do this this is very interesting i'm going to play this um okay we don't want to let him have that move yeah detailed calculation well it depends on what he can do because he can move the knight anyway um best move best move best move best move okay we don't want to defend that pawn we don't want to defend the pawn i don't think because if we defend the pawn he can do this and then it's kind of bad you guys know what i'm saying okay so we we can't ever move that pawn um shoot i do not have this under control guys yeah i know i know but he that was bad okay my night's kind of trapped in a sense so if i move it to a place where he can force his knight into my range and that's not a good thing and okay i think from running to a queen is bad he has to take with the knight now all i can do is pawn moves also if it like if it's a stalemate the person who gets stalemated wins so there's nothing to do i might as well pre-move this pawn thing so it's all on my opponent now let him do it he needs oh shoot okay now what i literally can't do anything to change the outcome of the game wait that's it he wonders he blunders all right uh okay that's enough of anti-chess i am slightly tired of that anything else we can do should we open up code forces again what's happened what have i missed has anything happened sure what's my final rank in the news 3 2 28 nice um let's see rating change is not showing you ping all top 10 rated people now it's not it's not that's mean let's just finish it here i think that's enough it's kind of late in many time zones and i'm tired after a while um yeah this was fun this was fun definitely i might do more streams like this well because the whole point of the channel is cp because um you know that's like my thing but yeah random streams could be fun too i guess um i don't know i'll probably stream more rounds in the future i'm not sure uh what else what other rounds we can do maybe let's see is there any upcoming app coder at coder if there is not then okay i don't know we'll do no no iq test that's too tired for that i'm gonna do terribly oh no no anti-chest channel anti-chess channel i'm not that good at it i just happened to win because nobody else knew what they were doing okay we'll see what else we do i also have to do homework which is part of what aaron was doing so i might have more time over the weekend just be able to do some random stuff maybe we can have it so you guys could just suggest some content like some contest i can do and then i can just do that and you guys can see what you want i think that should be fine yeah maybe we'll have it so i can you guys just suggest me a contest and then once we i suggest a contest to me or it can be some other things i'm not sure join the discord and we can discuss things like this join the discord it's in the description go to go to the channel and then open the description and see join the discord it's right here it's perfect just click on it and then we can talk about things and um i don't know when the next stream is going to be that's the point so we can just join the discord we'll talk about things because i have a bunch of people there and i'm going to ask what you guys want basically could you have long i don't know i might make solutions for that um it's kind of hard which is the point so i'm not sure how many i can get but i can try it anyway talk about this in the discord i'm tired i'm gonna end the stream here it's been fun guys i'll see you

Channel: Colin Galen

Views: 97,168

Keywords: codeforces, division 3, solutions, editorial, galen_colin, galencolin, round, 667, codeforces round, codeforces round 667, round 667, cf

Id: zgzEYMYZONs

Length: 235min 56sec (14156 seconds)

Published: Fri Sep 04 2020