[hard] Codeforces live coding

sound test one two three four five hello everybody and I will solve some of those problems I hope that today everything is okay with titles hard code for slave coding okay good as the title suggests I will do only difficult problems today let's have some timer wait so I will start in five minutes actually three minutes let's say until then there's some time to ask me questions if you have any [Music] hi Audrey boys hi asterisk how am I doing it's fine I'm busy like last few days because you know I have my normal responsibilities like a job plus also I do a lot of streaming and up solving event today in the morning I spent Maybe hour and a half on problem solving so I I understand already the solution to solutions for f and I want to solve one of I want to implement one of them this other problem colorful tree again I already solved so I will just go through it quickly at the beginning of this stream to summarize the solution for you I tried code versus scoreboard I've read the other problem but seemed difficult Where'd I work I work part-time in a high school just teaching computer science and also I work with companies like with Huawei I work with Huawei and I do workshops for their interns I help them with organizing competitions um so I'm this B2B employee how important is observing extremely important it's the most important thing during a contest you will mainly solve problems that you already can solve so there will be if you want real progress you need to up solve problems you need to solve after the competition things that you couldn't solve during a contest and in particular unless you're extremely high level it's okay to look at tutorial at the editorial after some time of being stuck because you will learn new tricks I've reached 2000 just by absolving I think you needed to participate as well so just by absolving doesn't work here and for everybody else absolving means solving after the contest it's it's a Russian phrase I believe okay time's up so let's go first I will talk about color for three again because I solved it today in the morning so I will maybe show this code enter I'm setting something up okay done cool problem G color for three again from type DB forces when I went for those problems I got up to f f was E and F were not that easy but the G was an easy problem and here's here's the problem statement you're given a tree and also every every Edge has some color and you're interested in that was a bad choice you're interested in colors that form a path so if there is an extra Edge let's say from six here to node nine then color green color would be not available we are only interested in colors that create a connected component that forms a path if we only look at this column let's say that we're given such a tree we see here one Green Path one blue path and one yellow path initially all the nodes are available and there are operations of blocking a note and blocking another note also there is an operation of unblocking a note after every operation we need to say what is the color with the longest puff and nothing there needs can be blocked right now the only available color is green and it has a path of length too let's say yellow is not available it's not that we can use this path from four to six we need to choose all edges of some color so they say there needs to be a path consisting of edges of color C and all edges of this color need to belong to the path we cannot not include something so right now colors yellow and blue are unavailable color green is available and its length would be the answer also every Edge has a weight it has a length but it doesn't matter you we can think about it as a unit lengths and we need to handle unblocking a note and blocking a note and after every change we need to say what is the maximum length of something of one color so obviously when we change state of a node it will unlock or lock some colors and the brute force would be to iterate all colors that are affected so if you have some node call it a and it has a bunch of edges four colors of all those edges you can update and you can tell them after blocking a you can tell them hey you become unavailable or you can increase their number of bad occurrences about notes by one so for all those colors we would increase their butt count so for every color for every Edge going out of a would say bad count of that color plus plus then for every color we would this way maintain the number of bad things for that color and separately we can store a set or multi-set the best lengths and while updating the bad count if it becomes zero or if it becomes one we erase or insert something to this global multi-set but this solution is slow because the number of neighbors of a can be B you cannot iterate all the neighbors and there is a trick for that first I thought that we should use Century decomposition here and yes it is possible but it will be a lot of coding but it turns out that here for all those colors of those edges they they are they create a group of one kind because they all meet here if we look at the previous slide let's notice that blue puff and Green Path they are kind of the same meaning they meet here in their LCA let's say and only one color that's yellow here is different in any way because it goes up so in general it when something changes for a note we say that there might be a lot of paths that have LCA here and I need to of course update them but then there can be only one path that I need to update in a different way because it looks like this and all those paths with LCA here in a nodes that I'm changing I will treat in constant time maybe if possible so in this note in every note I will store information with again a multi-set about all the paths that have LCA here I will keep here multi-set of long lungs of lengths of paths that have LCA here and if we ignore this node they are good meaning they are not blocked in any way so if some path like this yellow if all the remaining nodes belonging to this yellow path they are okay they are not blocked then the length of yellow path should belong here in this multi-set this multi-set exists for every node then the sum of their sizes is linear then there's this top note so whenever there is a change let's notice that there is only one at most One path that goes up from this color and it will have some LCA at the top like here and when we have red update in the red note we change its state between blocked and unblocked then this is LCA for which something will change as well multi-set of that white LCA at the top will change but that's a single changing that we can do in logarithmic time so the structures the things that I maintain is this for every color I maintain bad count and this excludes LCA so accept LCA because there can be thousands of colors that I need to update where their when their LCA changes so no if there is a path with 10 nodes this thing needs to be from 0 to 9 because LCA is treated separately also for every note I have multi-set of lengths of paths that have LCA here and they are good except for this note possibly so multi-set of lengths of paths with LCA here such that but count excluding LCA is equal to zero for every node I have that multiset and also I have one global multi-set and every note if it's unblocked it should give the its biggest value to This Global multi-set and that all can be combined and it just works so when there is a change of this note I if it becomes like it changes between unblocked and blocked so possibly its own multi-set its biggest value should be inserted or erased from the global multi-set because this node now is available or not and also I look at H from this node that is being changed to its parent here it's color white I look at what is the LCA of white what is the topmost node of white and for that one I change its multi-set because for the white color the bad count changes for example if let's say there was here a note and it was available let's say there was here a blue path also a Green Path colors actually should be only for edges also this note is now blocked and there is also this extra white color then what happens if when this node gets blocked well a moment ago but of blue was Zero but of green was one remember that is the number of blocked nodes of this color except for LCA LCA doesn't change white also has its own but let's say a moment ago right now for white but is equal to zero only green got some bad inside and now let's say that this changes so what happens is this in the multi-set of this note a moment ago the only thing existing was length of blue puff because blue puff is good this doesn't have any blocked things so there was a length here let's call it 4 and this is the only thing that was in multi-set for this node and now when this thing gets blocked I don't change this multiset this is still correct because this is set of lengths of paths that have LCA here and they don't have other blocked things also this thing doesn't change and this thing doesn't change because it would be I it would be very slow to update those um so this multisa doesn't change but what changes is this only if this note is is not blocked then this thing should be sent to Global multi-set Global set of available things and now a moment ago this multi-set contained F4 it also contains length of white let's say length of white was five this was the global multi set so this was from every node I want to get the longest path with LCA there such that this path is good now because this thing gets blocked this far we should be erased from the global set but it's still here also I'm I'm looking from this blocked cell I look at the color to the parent I see that this color is white I look at the LCA I update color of white bat of white from zero to one because now white puff has one blocked cell not including the LCA and then for this thing at the top the set will change a moment ago this set was let's say five and now I just erase it because right now there isn't any path with LCA here and such that this path is not blocked at all so also now maximum from this thing should be sent to the global set which is zero and this five gets erased but it gets erased in a different way than this four right now global set is empty this set is for this set is empty this set is far because uh this note knows that there is a path that goes through here with length of 4 and it's good except for this place and later on if ever this node gets unblocked then this far will get back to the global set so that's the solution and the code is here I have some helper DFS but the most important part will be this very small Global multi-set I will skip the initialization and now what do we have some colors are invalid because they don't form a puff but I here have actually I'm changing state of call of node a I look at color to the parent and if this is valid color so it was white puff in our drawing a moment ago I changed the number of but the bad count for this color plus one or minus one some assert I like asserts because if I make a mistake it will clearly tell me in what line there is a mistake I find the topmost note the top note of that thing I pre-computed that with DFS I look at multiset Sun saved for that node or the topmost node and the single value there can be changed so if that top thing is not blocked right now so it sends some information to the global set also if this set is not empty then I erase that it means if this node a moment ago was sending a message 5 should be in global set because it's available now I need to erase that 5 because we got something unavailable so we erase if but is equal to C it means that the bad count was a moment ago one and now it's zero so we insert something and that's where do I insert color C what is color C of that white color so if zero then at multi-set of that thing I insert something so that's the case of saying that this thing was blocked now it's not I'm unlocking that and if white path because of that is available now I'm inserting five back to this multi-set and possibly back to this global multi-set if particles one and it was Zero than the other way around I erase if when you use multiset you need to carefully erase and possibly I insert back to Global inserting from local for node set of possibilities to Global happens only if this note is not blocked because a local multi-set contains information about all the paths that we found here and they don't care if LCA is blocked or not so that's the logic you can read the code after finding it in my submissions if there are many elements in a local multi set in a specific node and that node gets blocked then wouldn't a lot of updates need to happen in global multi-set no because local think sends to Global only one thing if there is some note with a lot of puffs like that then it indeed contains in its multi-set a lot of value a lot of values like 579 but only 9 is in global set global this is nine and maybe something else from other things so when there is now a change of blocking this this multi-set I don't touch at all and I'm only sending information I'm aware that 9 was in global set erase 9. and that's common so this trick at looking of parents is one well-known trick another one and I would say this is similar is something like that like combination of segmentary and sets if you want to like practice an educational problem let's say that uh okay consider this problem there are end points x i y i and you need to handle online updates or queries that are find topmost Point meaning highest y coordinate with X lower with x i the smaller equal than something let's say something given to us this is given in the query and erase it this is a well-known problem let's say that everything is up if everything is up to billion then you will need to use coordinate compression here first and it's up to 200 000 x i y i up to 1 billion step one is coordinate compression on x so that it would get down to 200 000. and then build this is step two build segment three on X and for every x coordinate there might be multiple Y coordinates and one solution is this for every X keep a multi set of Y coordinates exist that existing there so if there is a 0.35 there is also 0.39 then you can have a multi-set with five and nine and in that segment tree where for every X you want to know the highest y you can insert the top value when something erases it you need to look up in a set what was the Top Value and send it to a segmentary removed from a set Step 2 create array array of sets of multisessive points can be repeated for every X the list of y's sorted by y and build a segmentary for this where for every X it should know the highest Y and then in such a segment 3 in the range of x's you need you can ask for highest y this coordinate compression is only still relative position of x yes exactly that that's correlate compression and you know on the level of solving problems like this G from code forces you need to know such a trick this problem should be easy for you and I think implementing this is a good prerequisite to then implementing this thing from a graph even though the difficulty is similar and we don't have any segmentary here that's not this this thing on the left okay if you have any other questions do ask and then we are done with colorful trigger now I will move to thing that I tried doing with DP but it was too slow and Incorrect and maybe I had some bug these are problems with some specific tricks the whole competitive programming is a set of specific tricks right so yes I saw that many times a lot of small things G sound easy it wasn't difficult F was more difficult but it's a different contestant no this one coxia and sequence during a contest I tried doing some kind of DP on bits but now I first of all understand the intended solution second I understand one more solution right I will explain his solution to me and I think it's easier to come up with in this problem we are given three values some of them are huge up to 2 to 60th power we need to count sequences of length n such that the sum of values is X bitwise our values is y and we oh sorry not count sequences we need to compare the bitwise x or of all such sequences bitwise or boils down to applying inclusion Exclusion Principle during a contest during well I try to solve it I realized that but in my solution it didn't help at all so I just included it as a dimension of DP but more important thing is combining summing elements with xoring and first I will walk you through the intended solution I didn't want to click that oh and while I remember if you want to help me you can after I'm done with any stream you can go to YouTube and in the comments you can write timestamps for problems unless somebody else already did that because now I have like five past streams from the last few days and I would prefer not to spend extra time it's not that big of a deal but still I would prefer somebody else to do it so if you see a stream a recent stream with no time stamps and nobody else yet in comments wrote down times times please do it thank you okay f okay so what I did realize is this if a of one is not equal to a of 2 then like you know a of 1 is 5 a of 2 is 3 and then there are other elements then also a valid solution is swapping those two elements so like that we can explain that we should only count sequences where A1 is equal to A2 and we can do a lot of observations like that a proper combination of such observations gives us a valid solution what but first of all inclusion Exclusion Principle we want the bitwise r of all the numbers to be equal to Y ins instead of that step one is to use inclusion exclusion and then the this thing it this increases the time complexity by 2 at Power 20 but because of that we only we have a condition that every AI needs to be included what's the character for that also this doesn't change this is in latex for set inside other set subset I'm just copying a character here you go for such this means this is a subset of Y because y tells us what bits are allowed because we want numbers to have bitwise r equal to that and by inclusion exclusion we change the requirement that it's equal to to just belongs to so a i every a i in binary form needs to be a subset of Y okay now second thing because we sum up bitwise xor I can focus on a single number so first try would be iterate every AI every possible A1 and for every value of A1 we can just count sequences from A2 to a n and if there is odd number of them then xor A1 to the answer because if for A1 there is let's say 50 Ways let's say that we choose A1 is equal to seven if there are 50 ways to finish the sequence then that's even and 50 times we will get 7 excerpt to the answer and so that cancels out we want to hear check if there is an odd number of ways to finish if so answer X or equal with one but we cannot we shouldn't iterate all a ones but we can look at every bit separately because A1 consists of a lot of bits and they are independent when we want to know bitwise xor of the answer we can look at position 0 position 1 and so on so to make it faster for every bit and 0 to 19. and so consider a of I bet to B1 this is simplified notation meaning the bit bit of I of A1 we just focus on one element is one and now we need to check if there is odd number of ways to finish meaning choose all the other bits of A1 and also all the other numbers what now we need to find this where the first element is a little bit special and there is that condition Let's Go full screen with that now this is this is some over such possibilities that the sum of a n equals X and here comes a trick and that's a crazy trick from editorial we are Computing things modulo two right because of that we want to add to the answer we will add this bit if there is odd number of ways so we can just compute things modulo 2. that always happens where when the statement says compute the answer module 2. here we actually derived at that but whatever so here everything I need to do mod 2. and that changes things a lot because I can consider all the sequences AI and I can multiply modulo 2 Boolean values like that Boolean value meaning a i belongs to y times Boolean value for you know A2 belongs and so on this is the product for every eye this means this is product just like this is the sum in even in C plus plus but also in math just if this you treat a zero or one you can multiply those things and only if all of them are 1 then this will get counted and you sum this up model.2 and now comes a crazy trick this thing modular 2 is equal or well rather yeah this thing this thing modular two that's equal to Y choose a i and this identity has for example a name Lucas Theory I was aware of that but I very rarely remember to use it during contests and usually the Lucas theorem actually provides a transition the other way around I mean if you see binomial coefficient you might think about Lucas theorem because Lucas trm says if you have a binomial coefficient you can write it down as the product of some things I'm saying something stupid no it's okay so as a product of things if you break it down into bits and like that you can prove that this is equivalent to that but for me it's crazy to this this thing write down in form of a product where you know there isn't any product mentioned here and then to say this turns out to be binomial coefficient I find this to be extremely difficult like it if this was the only solution for me this should be the most difficult uh problem in division one contest so this thing we can replace as y choose a i modulo 2 which is just zero or one we don't care about the value of this we care about its parity so if Y is let's say 100 AI is 37. I don't care what is 100 model what this hundred choose 37 I care only if this is even or odd because that turns out to be equivalent to checking if AI binarily belongs to Y if this is a subset and now if you look at this uh now from combinatorics we can argument how this is equal to something easier because if you have if you have I don't know why possible elements and from them you want to choose angle some value A1 equal to 0 or 1 or and so on up to y and here you have another y element and also you can from them choose A2 equal to 0 or 1 and so on then if you multiply how many ways you have to choose A1 elements from here times A2 elements from there then basically you can choose whatever you want so this is simply choosing from two y elements choosing like any subset which that would be just to add power that but also we have a requirement A1 Plus A2 equals X problem link I don't have that comment but we are solving this coxian sequence um now we want A1 Plus A2 to be X so it's like from now 2i elements we choose X elements and that's 2y choose X so here back to here this um if we want to multiply it by all possibilities of having a sequence AI that is simply and here we have sum of N elements and Y choose X plus we end times from y Elements which was any subset so in total from NY possibilities we choose X one thing was that we fixed a single bit of A1 so we actually there was some requirement about this guy I think we can do this subtract 2x power whatever that is because the A1 it a one we want it to for sure include value let's say four no that's wrong I wanted to say this but it's I think incorrect that it should be almost correct like temporarily from A1 I subtract this bit and then I add it back also from X I would subtract it but it doesn't guarantee that there will be a one there could be a one before I think that from y I should also exclude it were a few characters away in this slide from the solution since once we are it will be five minutes to implement it because the solution is for Loop of size 2 at Power 20. times for Loop of size 20 and then just adding to the answer this formula I'm multiplied by stuff from the for loops maybe this bit should be just straight excluded from y um foreign okay the first y will be special I think that it will be y minus 2 at Power B choose A1 multiplied by y choose A2 multiplied by this and so on so it will be just n y minus 2 at Power B choose x minus 2 at Power B I think that's it I will now check in the editorial if maybe not here here that works wait do I Prime as we pray oh that's just updated why so this is my way okay yeah that works so that's it I will move this to a side I mean just this formula I need to retype also those things this is f but that's another F I can just erase it we have test cases no nxy we'll have some big binomial coefficients to compute are their parity rather but anyway first inclusion exclusion for for all the subsets of Y if Y is if mask is submask why this will tell me if I should use -1 or plus one in inclusion exclusion and then for every bit and there are 20 of them why is that 20. because that's why is that okay so if y or even musk I guess but for musk equals zero nothing will happen and that's fine I want to save this if this bit is on but because otherwise it's not allowed we consider a of one or a of zero of beat to B1 now we need to check this guy first I've I'm tempted to implement that just with Brute Force maybe not now X is huge this is huge I need to compute this modular too so I think we need to use Lucas trm to do it only used inclusion exclusion when working with primes that's strange inclusion exclusion doesn't have that much to do with Primes in other words yeah I'm surprised by this okay and why is small enough yes it is and now if if a choose B modular 2. and then answer is int yes increase by two at Power B multiplied by if diff is odd then minus one or the right Plus 1. and okay let's just use Lucas trm I should remember it by now I need to check oh I just if one is subset of the other of course so return whether A and B is equal to B that's Lucas theory model 2. 0 not a good sign zero and zero ah also I want diff Y is free so we have subsets one two three those have diff equals one diff equals zero that's good what's this b b is the bit in this case there are two possibilities call and now we have from some formula 8 choose four seven choose three this is a subset this is not a subset let's verify that this should be odd and this should be even yes that's correct so modulator only those matter and they have a different div so they will cancel out one of them shouldn't know which one we have three elements that's a lot of elements to consider if sum equal to 5 I iterated all the triples with sum equal to X and what should I do with them okay 21 but what I wanted is to check something with the xor hmm also if n is even then maybe I should just print zero oh because at the end just answer gets multiplied by n so I think that well whatever so if this is zero then just print zero otherwise like the first element is like any of n elements there's odd number of them cool now there is this and I want to say if let's say this plus that plus this we will check how many have this bit on no just if this is odd count plus plus in all of them well of course if you add up three numbers if you add three numbers and the sum should be out then there is odd number of odd numbers I didn't need this to tell me so 21 is odd this corresponds to mask three b0 and this turned out even should be odd no but what I'm interested in is only the first bit the first element because I assume it is special and it's still odd while this is even so there is a mistake somewhere when musk is free this is zero b equals zero this is allowed three times this should then be why it should be mask foreign apparently it's correct and now I'm getting a correct answer why is it slow oh because of that yeah I still think that one line is wrong let's see 64 should be the answer and should it be so slow minus 64. why modular 2 am I using minus one can somebody tell me and why is it so slow because of printing I print and it takes time here we go works for the tests print minus answer great idea great idea well didn't expect that and what am I supposed to do with it why is this not used all right because inclusion exclusion I'm using minus one plus one module two it doesn't matter okay okay scary okay I passed few tests with answers equal to zero that doesn't mean much unsight long log but I'm not here Computing values bigger than 12 power 60. so sine long lung should be okay just in case though I will copy this which I couldn't do during a countess but I can now I would now get information about overflows if there are any I still think that this didn't work for the first test Dave doesn't exist this thing means that all numbers they can be from 0 to 3 this bit in the first number needs to be one and my program claims that the number of ways modulo 2 is 8 choose 4 so it's even meaning zero but this trivial count thing that I correctly here iterated triple such that they sum up to X and there are nine ways mask is 32 bit yes that's okay but you got me worried for a moment Y is up to 2 at Power 20. so this the things with binary operations they are only into type not long choose function operates with long log hmm let's see this is eight this is four eight choose for this does make sense if I ignore all the bits so just everything is arbitrary and then what was y A1 that was one if and only if this is subset let's check if that's true three choose zero three choose one three choose two three choose three all of them are odd yes they are because three is such a special case okay those I'm using Wacom drawing tablet R equals y inclusion exclusion gets rid of that check so by doing this I'm iterating subsets of Y and for each of them I'm only allowing subsets of something and three choose A1 this is supposed to track one or zero or one whether A1 A2 and A3 are subsets so this would be nine choose X was what X is five which by the way would be zero but we are counting cases where A1 has the zero bit on so here we have only two choose A1 and now the sum of them should be four not five why is it eight choose four is my code brute first code correct gets modified a little bit for every J for every k nine this output is correct but I still think that part of it is wrong part of what my program prints what if the first number can be only zero or two and they need to sum up to x minus 1. even so that's not equivalent why well because of that of course even and why is that not equivalent what if I say one and three eight so from 0 to 5 not to free oh this thing counts also bigger values there can be four or five if I want to actually count so what my program later sees it should be up to three X is not free so even okay my program works properly for this first test but it's a very easy test because Y is free now I want to get something that is a counter test let's see let's create a bread first I will test only using n equals three and return zero okay now let's just try something else three five five it worked three six five seven I will later make a for Loop if I don't see it in a moment if they I mean I don't find a mistake for zero okay that's a counter test just a big one free 7-Eleven three One Eleven three one three okay got the proper counter example I wonder if maybe one doesn't work for brute first I need to also say actually brute first for n equal to one accent y need to be equal for the answer to be non-trivial that's wrong right no excerpt yeah that's fine and this is wrong okay so n equal to one is a counter example actually I wrote that here well but also free one for is a counter example if sum should be one of one element it the bitwise r cannot be free and this seems to be an issue with my wait a moment inclusion exclusion was important here this is not modulo 2. this thing is outside of Mozilla 2. do I need answer is equal to absolute value of the answer okay I might be confused but if this works then I'm submitting foreign I actually didn't check if it works here doesn't work why did I submit foreign if mask if mask is equal to y so everything is allowed this should be taken with plus one this seems okay how could this be 64. pop count is 18 and 11. and maybe I'm hitting some overflows so it found something it found something non-zero only for a smart mask with 11 bits on instead of 18. so the answer should be -64. but why didn't you find anything for other masks and this is not fixable just by plus minus one here this is another issue I think they compile with wall of extra and so on there is wall but there isn't W extra so w all yes WX trundle and also known not not pedantic I think I tried that beforehand it was annoying all the warnings are annoying I guess this what I'm compiling includes overflow warnings I'm not sure about one to some power maybe this is defined maybe not but normal overflows yes they are included I'm stress testing this very very is a counter test um is there something smaller like two versus three or three versus two no periphery was the smaller counter test and it does work for the sample to straight no it doesn't work for the big test but I figured out it's because of some other reason because of the accounts okay are well wait a moment foreign what am I doing wrong should I maybe for every bit separately do inclusion exclusion to know if this beat should be taken with zero or one so should we hear XR I think that's it okay okay because the fact that for different masks I'm checking the parity it doesn't mean that I should add or subtract everything just means flip yeah okay so what would make more sense here is first this thing then investing some kind of parity using a mask for that parity and at the end saying only if parity then answer plus equal this and here I would not modify the answer here I would say parity X or equal one okay got it well that's crazy I knew a solution and yet it took me an hour I mean of course this first solution it would be enough to hear Change Plus to xor which makes sense if we're talking about things model to now uh quickly about the second solution but do I want to go through that radish told me another solution today so just very quickly about that and I think radiologist's code will match it but it's up to you to find it um for we still do inclusion exclusion of course foreign I think like we I wanted to do it in my first solution or we say this if n equals 11 then we have a group of eight equal elements then two equal elements then one equal element and we do inclusion exclusion so eight times I can do let's say anything anything zero anything anything zero then two times I can do also the same thing and one time I can also do the same thing eventually I will iterate over like one bit here so maybe let's say this is one now because this is multiplied by eight I can just add three zeros here this is multiplied by two so I should just add one zero at the end this is multiplied by one so just like that I need to now know the number of ways to fill question marks so that the sum would be X and I have here every question mark is a power of two that I can use or not this is just two it might have a certain two then I have a possible form which is here I have a possible for which is here I have a possible eight a possible 16 possible another 16 and so on and we have this there and now it needs to be equal to zero it to X and I want to know the number of possibilities 2 I can move to the other side so I have the sum of a bunch of powers of 2 that I can use or not and it needs to be equal to x minus 2. now is there an even number of ways to do it there is disclaim now that I we can group those numbers together if there is far and Far because of symmetry I can also replace them with 8. to 8 I can also replace with 16. 2 16s I can replace with 32. continue doing so unless you have I'm doing something stupid okay continue doing so unless you have something like a separate numbers let's say 16 plus 32 plus 128 and you want this to be equal to x minus 2 and you care about POS number of ways modulo 2. and that's possible if and only if this is like you can in binary form get this number from numbers on the left or in other words just like Lucas theorem says this needs to be overset of that I think I want to implement it just in case well why not number of solved problems doesn't matter right so it's more about learning basically the game of 2048 I guess just without the dimensions but that's maybe a good comparison like in number 2048 two same powers of two will transform into a bigger Power of Two and what's the time I hope that I didn't mess up the beginning because you know I didn't read the code and this part it's like well if it's zero one or one zero then obviously there are two ways so it makes sense but it seems easy right we don't even use Lucas trm here because we're just saying is there a way using those powers of 2 to construct this number well those parts of two are different so represent that number in binary form and see if it's there or not that's an interesting way to prove Lucas theorem okay let's code it so we have here go for bits that are on in n yeah I want to implement it that will be second solution this again is bit in the first number then there is bit in n oh and first we have inclusion exclusion again I'm not sure if that's that goes first I think it's safer to do it here this seems slow think it will be 20 cubic so I'm missing some step unless we can do some pre-processing to make this faster wait wait wait this I'm stupid if we have something like 4 plus 4 plus 8 and I want to simplify it by getting those numbers together and saying that this will be a power of two I can just add those numbers together I'm dense sometimes that's just 16. this process that I described it's called adding numbers what can can be a name for a math operation that takes powers of two and then interpurges them together like in the game of 2048 so that eventually you will get a unique representation of the sum as powers of two well yeah that's adding adding numbers together into looking at binary representation of the final sum sometimes I'm surprised by my own maybe not stupid it's okay not to notice something but it's funny to then realize that now if and and this bit is on this this means like we have say eight equal elements so we're looking at that now for everything with question marks here which is just basically the mask mask represents that I'm taking that so sum plus equal mask shifted by J I don't need those brackets right because casting is first than binary shifting and now if what is subset of what if some sum contains x minus this but also on the left I should subtract it and we here require this as well that's an easier solution isn't it 10 minutes of implementation there you go it's also slower because here we have a for Loop of size log of n earlier we didn't have that it's my actually my previous solution was it log squared or just a single log it was a single logarithm okay that solution was faster this one is slower but except that is accepted and it's tight one second and I got 700 milliseconds plus there isn't much you can optimize here wait wait did I'm doing something stupid here that's just I'm going for bits of n and if a bit is on then I multiply that bit by mask this is just end times mask huh okay that's the same solution I mean sure all correct solutions they need to be equivalent well that was interesting if you add those Powers together you get mask multiplied by n yeah because the sum 8 plus 2 plus 1 that's from definition 11. rediscovering summation and multiplication exactly welcome to the stream right I wonder now if radiosh realized that 156 that's no okay he realized that n times y I wonder why this is significantly slower but whatever um so one hour and a half in and we are done with one problem that I only described how to solve because I solved it in the morning and another problem that I knew a solution for I just need to implement it so this is done this is done and now I need to choose from graph coloring bracket and scoreboard I think that scoreboard is the most interesting bracket seems difficult but I also saw I may I saw a spoiler I saw one tag on the right right now I hit I hide it hit it what's past form of height I hid it but I know an important algorithm that needs to be used and F1 graph coloring seems boring let's do scoreboard and that will be the last problem today also I counted that including this problem from a moment ago in the past few days like past one week I think that I solved 40 problems in code forces in past week and it's not that they were all easy problems on one hand that's nice I'm practicing on the other hand strong people when they just participate in those same contests they they do the same number of problems just during a contest well I instead need to spend two or three hours plus a few hours of solving and seeing Solutions and then implementing which is sad still I shouldn't complain just from time to time I perform well enough that I get to the finals or I win something okay scoreboard so we have here and problems that we need to solve at least I'm solving them it could be worse I'm aware that I'm in 0.1 percent the top people I mean less than that but still everybody will keep comparing them with themselves with somebody better I wonder if now tourist Compares himself with like his former self from maybe three years ago if he used to practice more because tourists used to just win everything and now he doesn't so does he feel bad is there now no single person who is happy with their overall performance I'm using your template for debugging and very nice but I'm not understanding it that's fine you can change Emir which is a Polish word to something else okay what do we have here we have I already spent 20 minutes on this problem there is time and we are given n linear functions all of them decreasing this is not a linear function this is and at every moment of time at every time at every second like here here here I need to choose one of the functions and I get a score from that function I need to maximize the total sum of values that I will get and I cannot use the same function twice also the function continues flat after getting to zero so maybe what I should have done is this this and so on so it's not that you will lose you will get a you will get some value from every function here in the statement they actually wrote something like a function is will get you maximum of AI points comma bi minus slope times time but you can easily move AI outside of the function and then you will maximize with zero and this is new bi Prime let's say so this is what I draw is after some simple reduction there are functions linear functions dropping down to zero then being 0 Forever at every X you need to choose one of the functions uh the different one and you need to after n seconds you need to maximize the total score here maybe it's optimal first to choose the white one then to choose the green one then to choose I'm guessing blue or yellow then to choose the other one blue or yellow and then to choose green now green must take it and so red I claim that this is optimal here and what I used here is the fact that usually the first that should be taken is the something with biggest slope something that is very steep white loses points a lot so if you ever want to take white you should do it at Time Zero unless something will drop to zero and then you're not in a hurry so for all of course if something drops to zero then why bother take it it will give you zero score after that transition from before so we are actually ignoring those parts with zero and just you have a possibility of taking something or not if you don't do it until this moment then you just get zero and there is this trivial claim um that you we should sort by slope and in this order take them but also for every function we have a possibility of just not taking them here's an example imagine something with very something very steep here but also very low and at time one it will eventually drop down to zero it's not beneficial to take low score here and because of that delay everything else by one second or one minute so sometimes you should drop things and now after you start by slope for every object you take it or not and there will be some time that already passed which gives us DP of I and J where I is ID of a function that we're currently looking at after sorting by slopes and J is how many things we already used or in other words that's the current time and when you are at I time then you have two possibilities either skip meaning move to DP of I plus one time or take which means move to DP of I plus time the I plus 1 time plus one and if you decide to do it you also increase your score by the function the dysfunction you don't even need to maximize with zero because dynamic programming will figure out that it's not optimal so here I can just say B of I minus time multiplied by slope or slope okay and you are at the end the answer is Max of DP of N and here whatever that's a trivial quadratic DP and we want to optimize it and the intuition says that I mean there are different DP optimization techniques and the only hope for us to optimize it is if there are some properties that are maybe not trivial to observe in particular this function of time so if for every DPI we look at different times and we want to know what is the current best thing that we could get this might have some properties like being convex or concave so and it has nothing to do with the previous drawing the previous drawing showed the input this shows some abstract function if we have a fixed I so we already considered maybe five functions and there is current state of DP for every possible time there is our DP value at if time 0 meaning we haven't used anything yet then the score is zero and then I'm guessing that the function looks like this I mean if you can use one object it will give you a lot and then its diminishing returns so every next unit of time gives you less and less eventually it would give you a negative um contribution maybe we will just drop that I I didn't think about it much but maybe this should be ignored depending on what is easier to implement thank you for recent streaming you're welcome um but and I even looked at the beginning of the editorial to confirm to myself that indeed I'm going into a right direction and yes the editorial confirms that something is here convex or concave during a competition either I guess it or I Implement a Brute Force to verify that on thousands of random tests and like that also you can check if always the differences are decreasing so what what my claim is is this and that means convex DP of i t plus 1 minus DP of i t is greater than that that's what we are verifying the sorry t plus one this means exactly that this height is bigger than that one or equal but for me it's not enough so I was stuck here I didn't go further into editorial I mean I'm aware that this should be optimized but for me it's not enough I think that I would want even that like next level derivative to be monotonic so not only I want this to be convex I would want the derivative of this function to be convex or concave because if we look at transition for a fixed I of course this okay there is this constant and then there's slope k so for time equal to zero this just increases by bi then for time equal to 1 it increases by b i minus k i and so on it keeps decreasing but that can arbitrarily mix with those slopes unless we claim something stronger so from this thing the transition will be by just plus b here to some point this is plus b but from here the transition can be is by plus B minus k from here it is plus B minus 2K and from here it's plus B minus 3K and as well it can now go down I think uh so what this problem is solvable if we can claim that some prefix for some prefix it's not optimal to use it and for some suffix it's optimal to use it or the other way around because then we'll do something equivalent to Binary searching but in my opinion this can be mixed and I can write a brute first to verify if this perfect suffix thing is true but even if it turns out correct I don't like how much I don't understand the nature of this problem another way to look at it is this for every DP State you will do this transition or this transition right like one of them maybe we shouldn't say is better but maybe we should look at transition backwards for every state it was created by some transition skip or take and now there is this crazy claim that maybe for small times they are created thanks to skip transition and for big times they were created with tag transitions because maybe for a smaller time skipping the most recent element like what's required to keep such a load time because otherwise something else is better and as I'm talking about it it seems reasonable right if you have more time available so far so if you had 50 functions and you are focusing on the most recent function but you could only use 10 of them because time is equivalent to how many functions you used among the previous functions if you could use 10 out of 50 maybe you then use the most recent one and if you used 20 out of 50 then it's even more reasonable to use that on the other hand with bigger time every next function is more penalized so maybe it's the other way around yeah exactly so we get bigger and bigger penalty it's time equal to Infinity we want to take it I solved the problem using zebi algorithm can I share it uh you mean this problem you can share a link to your submission is there somebody in the chat who knows the solution and can confirm what I'm talking about with those going up and down is there some property that holds here or is it possible is my drawing possible or not we want to maximize I think here it's very frequent that this will be below because already you found earlier something better something with a bigger B those first few it seems intuitive that there will be below but also at Infinity hmm so we hope that eventually we want to use it um oh so I'm saying that with big time there is Big penalty but on the other hand previous elements had bigger penalty previous elements had bigger penalty interesting so they I'm better than them at being used here on the right okay okay I'm starting to believe that starting from some point I will always be better like that I think just I like I have to say that in English treated myself I confused myself I made myself think that something is incorrect but it seems okay foreign now if I have some slopes and I'm searching for this first point where something is optimal so there's something like bind or search I think I need to use okay so we hope that this is binary search we'll keep those slopes we buy their search we find this proper place and here we are just we will shift this part of the drawing up and right like this new drawing we will find a place where we should insert our new slope then we'll take everything here we'll shift it like that we'll add this new slope those slopes do not change so it's like a set but a set that allows us to do binary search with indices I will first implement it using a vector um don't take this into consideration at the beginning I explained how I get rid of AI oh and again in this I'm not able to highlight a message can I highlight this thing yes I can I cannot highlight your message so again a test I'll cross oh Crush can you type again the same message and regarding your question I at the beginning explained how I can subtract a I from such a formula to get rid of it and to just say we are maximizing with zero second message worked so what's the difference this is just copy pasted I guess that just back of that software well if it's rare that's fine um so some solution use ply tree yes this will be tripe or BST I don't really know how to implement strips I will I will use BST because I know BST IX break it what's that oh special characters but I'll cross copied the same message so you know this thing worked the previous message with exactly the same thing character by character didn't work so no it's not about special characters I think it's just software you know the breaking for a second from time to time and not registering message I even have a theory if I hear a refresh that one occurrence of a message will disappear yeah here we go the software didn't register that previous message and it's weird I agree your new weird again didn't register but that's because I refreshed okay now can I there I remember how to implement BST and will this do the job foreign yes but it will take some time a first Vector solution certainly we have http test cases everything will give me B and slope K those are just pairs k d a no anyway plus equals a and do that this is how I'm getting rid of a I'm subtracting lies push back slope and the starting point then sort decreasingly right by typing R begin our end I'm doing this decreasingly from biggest slops wait yep that works and now I want to First will I keep a vector of slopes yes is it true that everything is in here also yes um unless it's at the end okay this is long initially it's empty and it just means that there is zero at the beginning with no slopes then for every line right I wanted to do tie let's learn that this is slope comma B does this compile no okay out so I should have should I ever use a word tie oh I see what about anti -anta is not needed I want to find the first moment where it's better to use this so far if this is at the end or let's see I will hear lose B minus I times slope if this or this is better meaning bigger then insert this here and break that's the end I want to know the top Point first let's just print DP it should be positive values and then negative and positive values Plus anyway should be the answer that's too big the answer isn't so big but it's decreasing at least unless I should just add everything but that also doesn't make sense this is 25 it's huge I want to read into the second test then the correct answer is 53 well it makes sense from everything here I take one for free that's 8 9 19. this is fine then what's the order K and B the second value is B and do I start in time 0 or 1 one that means that we should in my code at least do this as well even anyway should be decreased by that 21 81 so I think that right no that shouldn't this is fine okay now this is 7081 we get 71. which suggests that the first minus three should be used that would be very strange what about that 19 5 no 35 45 50 56. again the next negative number should be used y around 4 billion this is around 4 billion and 120 199 this is too big I only can use those so something seems to be wrong I decide when to look at editorial when I'm stuck for a long try a long time that's it as long as I'm investigating new ideas what's the point of looking at the editorial sometimes I want to just save time but it's an educated decision I want to test it for something very small and I don't like how big those all those tests are for now let's say one test one k b a slope is thousand B is 5 a is four and let's implement this also 99 is correct zero if I take it do I lose 999 no why is that okay oh so this is like doing one zero and you're losing 999 indeed if you take it after one second okay now if I place that with one and this with 50. this should be 49. correct and something more difficult slope 2 value 100. first we should take this item because not this item because it has a higher stop we'll get 98 out of that then next this 48. so this seems fine do you want to analyze this big test I can implement the normal DP as well and just treat it as a Brute Force because here I tried immediately doing slopes [Music] maximize this state with just my value by skipping this one and maximize that state with me plus b of I minus time times first this should be valid Brute Force 143 what's that test that's wrong missing end near B and now here you don't need and I mean for Speed purposes sometimes you want to do it but it doesn't matter if it's a single element here this thing here Ampersand here was necessary because I wanted to modify a here it's optional for Speed um I'm not adding anyway [Music] and that's still incorrect slope thousand b50 A40 oh first one 40 correct 5 50 40. should be 45. [Music] and here it should be 5. so it falls that it uses time equal to two oh because I'm already subtracting here so this is enough because I subtracted once there okay we have a valid British now that helps because I can get back to my smarter solution and try smaller tests I want to run them for into and one of them didn't print anything age doesn't print anything but also it will be correct so 26 26 done after counter test now we need to simplify it I'm trying to make a mistake to be bigger than one if possible but I'm guessing that's because of the slope okay now it's optimal to use bigger slope first so after one second this will be 25 and this one after two seconds will be 46 and that's in total 71. which brute first claims h 48 and 25 so the total is 73. 48 this at time 0 works oh we need to those slopes do they change as an extra foreign 25 we first considered this guy and it knows that the slope is 25 and that's cool then from 0 to 48 and we still claim 25 but this shouldn't be 25 this should be 23 so we actually need to decrease that slope so it's like modifying that but K extra um I think that once we find this all the slopes on the right they need to be decreased by K by the slope which I will explain in a moment but that's bed okay so the thing is the reason why I needed to do it I'm out of pages here's the situation when we have our drawing tablet was tilted or we have our function Maybe maybe here we realize that it's better to use the new item the new thing but and we claim that then it's also optimal to use it anytime hearing the suffix but it actually won't be used as the second one it will be used all always after everything else so if here I'm using something like B minus K as the formula if I decide also from here to transition there what will be used is B minus three times k when I use it so this difference here this is B minus k no this was some old difference it was DP of one dp1 I'm this thing this is dp1 now in red this is B minus k and if from here you want to use it you need to sadly use B minus 2K versus here there would be dp2 and now the difference between this point and this point is not just dp1 it's dp1 minus k so hence my minus K and also similarly here we will apply B minus 3K and again if you compute the difference between two yellow points it will be dp2 minus K and so on so not only I need to binary search something in the middle as this kind of let's say linear function I need to then modify the suffix like that well it's fine I guess I will submit this just to get time limit exceeded to confirm that I'm not doing something wrong wrong answer would be a reason for concern yeah running on test 15 I will get time limit here yep 16. okay and now BST can do that I wonder if tripe or Link at is easier no can this be static how can it be static how do I always implement the binary search tree like self-balancing BST do I use pointers I think so can I use this without pointers not really and do I want to implement this today yes I want to implement this today okay let's go then it's Maxi function no this was needed for Brute Force the BST that I usually use is called scapegoat tree you can read about it online maybe even on my YouTube channel there is a video and I'm not thinking about functionality it needs to know the size also something like one element right most element oh so size will be related to index in some way but also TMP greater than DP I need to know let's say the last DP let's call this just the right boost because note can represent a lot of things below this will be the last of them lazily I need to be able to add something so there will be lazy left child right child and maybe that's it then most basic thing is searching for the element where we should insert this thing something with the given slope and B foreign will either have both children or not or I mean both are zero and find what what should fines do actually it should modify there is slope and B at the end I should insert minus infinity or something like that so it would always be found that might be a good trick then this is fine so this should work right yep that simplifies the situation if this is the leave then I found it and I need to just before insert myself at this position I'm inserting that thing I will copy this paste it here for reference maybe else I need to decide whether to go left or right and for that I will ask my left child if it will find something that is enough to kill that guy also we need to pass the current index I this is how many things on the left we already skipped initially zero so if left once of this then left find else right but we also skipped things on the left so I'm grabbing left size for that now though my subtree want to accept this line that is true if I have below such an element that this is true so I need to check if I will just compute the TMP that's B minus I plus the size minus one because the last element is in size -1 times slope what am I doing TMP is greater than what than DP this is the right most okay if this is the leaf then still as a two do I need to do balancing of that tree first when I implement it it will be quadratic if this is a leaf I need to add a new left child right child so on I can just build anyway I need function for building oh and lazy I for now I'm not using lazy to do use in find or maybe help desks aren't strong enough it's almost impossible that in a real in a serious competition solution is something like a trip or BST and they don't create a test where everything is increasing or decreasing in some way I'm sure that I would be able to create a test in one minute where this will break so no I I'm sure I can bet that this code will first get time when it exceeded if I submit it okay built if values empty then no not values empty if size is one that stops spamming with the same question that is zero I think they should be null by default here but I'm not sure what I'm rebuilding foreign else we need to does that compile yeah left built with sub vector from begin kind of middle foreign to the right half I'm passing the other half of the values what else lazy zero anyway lazy zero so and anyway DP is just values that back and anyway also this is true am I done okay in this case we built using value that is here right now which is DB but first just before it we need to insert this thing also left equals null should be equivalent to size equal to one so I can check that if it fails I know I did something wrong when creating trees what an eye building I'm I'm implementing self-balancing binary search tree this particular version is called scapegoat tree you can read about it in Wikipedia it's a fun it's first it's a binary search tree but scapegoat means if any node is not balanced it's heavily not balanced it rebuilds everything below which seems stupid but it works fast this was always easier for me to understand than rotating notes so what do we what are we inserting we are just inserting that TMP and TMP is simply this here Size Doesn't Matter because size minus 1 is 0. okay we need to return and while returning everything that we skip on the right should be decreased by slope including this one so after I'm going left we need to say this right add minus slope so I went left on the right there is a suffix easy now when we get anywhere if Leaf that's trivial else I need to First push add my lazy right at my lazy lazy zero also after I'm going left and right I need to merge them and to merging them is just about while updating the size and DP or just I can say merge lazy should be equal to zero at this point okay I'm using lazy this is right most adding leafing once merge okay this is correct quadratic codes I think and I hope initially I want something with just one element there is a root and I will just put values on purpose I'm not creating custom comparator as our custom Constructor this is convenient for some other reasons the p is just this value lazy is zero and then no no slope and B and I what I want to get first I can run it to see if it doesn't break memory leaks are fine I'm not clearing memory so that's okay generally it's bad but whatever difference from segment review laser updates BST is dynamic meaning you can add new nodes in a segmentary you cannot create new notes you cannot just add new notes like at the bottom on the left and on the left and on the left in BST is more like a set because I got solved in 13 minutes so he won the competition right it was this one where radheus was winning and but he failed on sisters one problem if this works first first try then I'm doing okay I will do it below one hour print foreign I want to print the bst3 without affecting the lazy values because I don't want to make this work or not work just because I'm printing so instead of pushing lazy values I will do this where this is a leaf print pushed plus DP else go down also pushing lazy values minus infinities so nothing new is added that's bad we often run build on multiple values including sometimes normal values so it shouldn't be the case unless I'm not printing spaces no I am printing spaces what size of the tree at the end two if it's true then why do I see only one value it should be more than two does building work I hope that this doesn't get destroyed in line 60. hmm root size is 2 and leaf is true something is wrong with Islip function okay here we go the return that size is one now we get a lot of values let's remove those unnecessary lines and let's compile without sanitizers I don't care about the size and now did we see those values before I don't know maybe uh now I want to add them up to anyway and that works I'm proud of myself of course less proud because somebody solved it in 18 minutes but brought now I should get time limit exceeded because it's not self-balancing and I don't care that I'm getting you know wrong submissions well we passed more tests good now I would be pissed if I got accepted with this D because it means bad tests weak tests now now we need to make it actually into a scapegoat for now it's by binary search tree kind of just some kind of dynamic I'm not sure about the proper name no when we exit from something so we do merge we should say this if not balanced then I will change print to maybe DFS values is DFS and build of values that's the whole trick that's the whole idea of escape goat tree where first we have is balanced function and I should run this only for non-leafs let's say no if return left size left is smaller Eagle two times R plus five and the other way around this means these three this sub tree is balanced okay and theoretically for best time complexity you should just put one here and there but five is better constant factors so if you see that some tree has three things on the left and one thing on the right it's not yet worth rebuilding if this then the values push back plus DP else run here and run there values values prints called DFS and that should work making this stuff self-balancing seems like hella work not really that's like the easiest part of this well I messed something up but it's it took me three minutes to add that so adding making this self-balanced is not a big deal well I messed something up and I made it slower unless it's just a constant factor I don't think so it's possible that never we run this but let's see left size right size sometimes we run that am I being stupid here I'm now wondering if I messed it up doing this from the bottom and that's what happens here is not so efficient but I think it still doesn't affect the time complexity don't pass values to build by value where is built I mean it shouldn't matter and how do I avoid passing them by values this seems to be a constant Factor like n gets then split twice split twice this is n log n and just I'm making space complexity and again if I do what you are suggesting with Vector Ampersand then I cannot do that because notice this is not an object and I can add some extra few lines I what I want to do first is I want to generate a big test to see what's going on can be a a is smaller than b I know this infinite Loop something is wrong with my input right taste cases this seems to be quadratic I'm doubling the data size and it gets more than four times slower hello not so lazy I messed it up so it's not about constant Factor how could it happen that it's so heavily unbalanced five thousand versus two hundred if I'm adding something below then I immediately check that this is impossible no call to left out no because we are adding in a suffix also adding should be independent from the time complexity that thing is okay what we are doing is we are finding some position and all everywhere to the right of it we increase it would be the same in this segment tree if you wanted to find some special position I and add plus X everywhere to the right foreign like with the function is balanced [Music] two doesn't exceed twice R plus five R doesn't exit twice L plus five what if I be more if I am more strict okay so what if I just say R plus three and plus three till how does that happen should I use here r no it's balanced now it's balanced no matter what I run merge and I check that do I add notes in any other scenario at the beginning find function find is able to mess up balance of my tree what if I say here one more way okay another approach Rand modular size this this is yet another version of scapegoat tree the answer changed right maybe not well I will submit this but this is suspicious oh and run doesn't work in code forces ah do I need to rebalance all the tray whenever I see a place with big imbalance then I fix that place hmm well it worked better than what I had a moment ago so there is a back I think that the back is in fine function still worse than unbalanced three by one test yes because maybe I'm spending time on something that is actually stupid or pointless wait what I don't run build I do when I see an imbalance I run for that tree with DFS and I didn't actually rebuild it not an optimal BST this this line was missing so when I see that there is like one note on the left five notes on the right I collect the six notes and I don't do anything with them and they are still there accept it yeah I wonder if this is also good this has a name I don't know if this is called something like dynamite BST so instead of caring about anything you can always say this if subtree has size s you can move probability 1 over s or build it and the average time complexity expected is good you wrote its big beat got deleted yeah when I changed the style of doing something I modified few lines there like earlier this would look differently I didn't have DFS I don't remember so it's accepted with randomized version it's also accepted but this first is better and I believe that the diff from let's see from this code to this one should be just one line I mean here I added a few lines but it's the same no wait oh no it was to Discord so this was not balancing then in three minutes I corrected to this thing and then we required one more line so let's see this thing compare in the comments yeah that's only that line because that got removed I'm I say I tried difference five whatever it's age soft editorial I'm guessing will describe something similar so they are saying I didn't read those formulas that's a formula proof so I got here that it's convex use the trip to maintain this sequence which might be called the slope trick well I'm interested in this part of the solution and still I would appreciate separate common discussion for every problem otherwise it's difficult to find something okay so in LA in the past week I solved I think 41 problems I will update oh why is my stream not here so was it down the whole time in code forces oh that's a pity because code versus users are the main audience maybe I was like one minute late but I thought it was like this it was displayed at the beginning where's my blog post here so now soft and soft what is left is those two and maybe for clarity removed that and I don't want to refresh the post cool okay I'm reading the chat now am I planning to participate in live contests yes but I want to I need to have time also I don't like three hour contests in code forces and the last division one round the normal two hour contest without mixing with easy division two problems was I think four months ago so code versus holds normal division one and separate division two contest only once every few months and it's difficult to get one and like last Sunday which was yesterday I couldn't participate because I was busy during the round okay I haven't seen a video on this you mean something like this BST yeah you need to know something some BST or some trip I think trip is randomized BSD I believe that the stream was nice I'm happy to hear that it was difficult of course so it wasn't for everybody I need to remember to take a look in the middle if the stream is running so also tell me if you are watching my stream and it's often code versus problems and during a stream you don't see this on the right side of code versus tell me so this is profile of what of somebody who described and the technique oh so he's using python okay never mind I thought that it's something related to BST hello whoops when is it time to learn strategies and Algos and once you get the when you're during a contest you get to problems that require something this is a time to learn it you can lazily learn things whenever you encounter them in a real contest but also code forces shouldn't be your only platform code versus is too Muffy where you're on a break last year not exactly a break I was just doing other things my comment on joining Google well right now I'm sure Google doesn't hire so much as few years ago but yeah somewhere in my frequently asked questions I talked about it right that's why would I join Google which company's programmers I look up to they are the people in the top are smart it's not that I look up to something in particular I know people from Poland better of course for example radish is a beast he can as a single person he will be in some ICPC contest of course he's strong okay stream is over we solved three problems which is less than I hoped so I hope to do but that's fine I think there will be one more stream this week possibly on Wednesday I'm looking at my calendar yeah I Wednesday maybe Thursday but most likely Wednesday and I don't know maybe I will absolve those two problems but I hope to do it until then just outside the streams maybe it will be a new contest and that's it for this week because we on weekend there is a competition in Poland I'm participating in so I will be out of Warsaw boom you can for example in twitch and maybe also on YouTube there is a link to my calendar if you want to import my calendar of streams into your Google calendar but I only put something there once I am certain about the stream and right now you know I don't know if it will be Wednesday thank you all everybody for watching remember to also absolve your problems what I was doing for the past few days it should show you how you should practice I participated in few contests virtually usually but I tried to solve the difficult problems anyway and right now because solving easy problems isn't very educational so right now I have here 8 out of nine eight out of nine five out of six five out of seven and I want to solve one more six out of eight and I want to solve one more plus there was an ICPC competition I also did have a good even

Channel: Errichto Hard Algorithms

Views: 18,921

Keywords: codeforces, competitive programming, algorithms, coding

Id: jh7ISwaUOws

Length: 182min 52sec (10972 seconds)

Published: Mon Jan 30 2023