hey there it's code for round 957 five time okay so this is better oh come on yeah I need to this okay oh need to end I don't need end show down this not must K not greater than M okay the sum of FIS minus the sum of GIS this is just easy CR very simple CR so you want more F you want less G so what does that mean for this one okay e for for oh in totally you're just to creas strategy for jumped up to end we should greedly go [Music] to small yes to this wait oh I didn't do the key for what the hell what the hell is this so n * Aus B has to be tiled with n n * a is at a million 6 wait so now I can do a n * Aus Bal value so just be well please second my most and all time SP L * Aus B = 11 then yes now good this is huh inter start what oh let's see for okay so next we track the each one is I have to not take yeah so then yeah that works that works so where you take the product gcd with this even easier okay correct for is that oh exactly than prop has to be exactly than h we have some napsack check going on so obviously how complicated Tok 128 divisors oh I see we just and just kind of DP it okay got it so for for for for oh that's gross why is this wrong why is this wrong for oh that's tricky I myself to use it more than once that's gross okay this should be for what some of next just take every subset B B+ one for for [Music] so 2+ one is one for oh yeah it's really two * size plus one it doesn't really matter given let size pick a size 4 6 s for to be pretty good number right so let's just like this how many ways are there for this to answer so it has to be noted and then OB there have size plus the one that are not is that the answer no two for for what I'm down by one what is that I don't know why but appar that's not right it's three okay can I figure out what's wrong with this so so I just want to mexus 2 SI is two the M three oh are you including the empty subset oh wait one is full okay then this is just spr yeah if I don't do this I they all don't work okay cool all right so we won this contest and uh actually hang on uh actually one more cool all right so we won this contest and yeah nice little set of problems um let's go through them cool so start the problem a and basically we're doing a * B * C and at most five times we can pick one of them one of the numbers and increase by one you want to maximize the product at the end um yeah this is just a simple greedy basically the idea is if you have a * B * c um basically we're always going to increment the smallest number because if you do this a + 1 * B * C you get a * B * C plus b * C so obviously GRE ideas to have these two be the biggest two out of the three uh this doesn't prove that doing it five times this is the right strategy but that also happens to be the case U it is still the right strategy even if you repeatedly iterate U but yeah if you don't believe that you can also just try all the different options for spreading out how to do um adding five it's it's not that many um I guess probably some people wrote like code that just you know it's like ABC and then they just take the max of a plus 5 * B * C know a plus 4 just a whole bunch of things that could also work um obviously takes a little longer um but yeah this code pretty simple just find them in increment it and then you're done cool yeah I'm just going to go through these pretty quickly um all right B yeah so B you can break things you have a bunch of what is it sticks kind of and then you can break one into one and a a minus one or you can attach one to something you want to combine everything together yeah so this is another greedy the IDE is we're going to combine everything into the longest one uh because I mean yeah basically everything else has to become just one since you can only merge ones and the longest one is the best one to keep intact so that's what we do we just sort everything and then for a given value of a if you need to um yeah if you if you need to break that up into ones that that takes a minus one steps so for example if it's three you need to break into one and two then you break the two into one and one and then afterward you need another a steps to combine with the biggest one because you're going to one by one merge each of those um yeah that's it we just add this up and you're good that's answer in fact I don't even use n so it's a little silly but yeah um that works you can also you can actually you can do this in linear time instead of sorting because you only need to find the max element it doesn't matter the order of the other ones you're just need to find a Max um cool that's B moving on quickly C this is yeah you want to maximize the sum the problem looks a little scary but if you just think about it you just want to maximize the sum of f minus the sum of G so you just want to increase f as early as possible and increase G as late as possible and yeah I mean this is just a simple greedy turns out those two goals don't conflict uh because basically you can you can almost just put a reverse sorted permutation where yeah you you use the biggest numbers possible first which means you increase f as quickly as possible first because f is the sum of everything at least k um on the prefix so yeah so you want the numbers as early as possible you want them as big as possible so reverse pration makes sense there and then the only thing is that for G later you want to increase as slowly as possible so you actually want to because basically for G it can add up the numbers 1 through M you actually want to reverse 1 through M so for example for 10 38 what I would output is 10 9 it's it's not exactly this it's similar 10 987 6 54 1 2 3 so you can see that you know here this is the key thing having 10 out 8 and having 1 2 3 here the order of these numbers doesn't matter that's why in the output the sample output they do this but yeah basically what I do is I make this permutation 1 through n reverse it now it's n through one and then I reverse the last M values so it'll be n through n + one this is very confusing sounding then one through that's what it's going to be uh cool that's see D so D we we are jumping and swimming across not across through I guess through a river uh we can only swim K meters in total at most we can jump up to M but only from land or logs and we have to avoid crocodiles entirely um yeah so again this is just a greedy strategy this a lot of greedy problems basically yeah for convenience I put an L on both sides so the banks are logs essentially if we ever end up on a crocodile we lose otherwise if our current thing is water we have to swim one step ahead and then otherwise we're on a log and we can do a jump so for the jump uh the greedy idea is if there's any log we can reach we can jump to we should jump to the log cuz it's always better to be on a log because you can jump again uh otherwise we jump to the farthest water we can get to uh farther is better because then that way we do less swimming um and then if we can't reach log or water then we can only reach C crocodiles which means we lose um yeah so just pretty simple there just a greedy approach um yeah just need to commit yourself the 3D is correct and then Implement and we're good cool and then yeah the fact that m is small helps with the time complexity being small um but yeah you could actually speed this up if you need it it to be faster but at least for this problem you don't need to do that all right problem e okay yeah this is a weird one um basically you you're given n and you want to compute How many pairs A and B there are where n * a minus B is equal to this incorrect calculation of n * Aus B which is you take n concatenate it a times and then you remove the last B characters from the [Music] string uh and N isn't too big only up to 100 But A and B can be up to 10,000 each so you can't just iterate over all AB pairs because that would be 100 million that's too many um so instead if you think about it a bit uh you need this value to be it has to be a prefix of n concat with itself over and over right and also it can't be that big because this is at most 100 and a is at most 10,000 which means it's at most 1 million and then minus B which is at least one so it's less than 1 million for sure which means it has at most six digits so actually there's only six prefix of this that could make sense um so what I first do is I iterate over the length of the result and then that take the string V that string is just going to be you know our numbers um digits over and over until length and then now I know our goal this this value is our goal right um and so now that I know our goal what I can do is I can iterate only a and then I know what B is because I need * a - Bal value so B is just n * Aus value right so we get this and then we just need a little check B has to be between 1 and 10,000 um you don't actually need to check this part A * n because you already started with this and then yeah then we need the length thing to work so we need the length time a minus B to be the number of digits we're going for if both those are true then A and B works and so yeah that's it so this is just instead of 10,000 squar we just do 6 * 10,000 um which is much better and yeah that's definitely fast enough um and yeah just output them and we're good cool that's e what they change all okay I guess they just got a lot of confusion around this cool problem f um we need to take we have a list of numbers we need to separate the numbers into segments where in every segment the segment is bad bad means there's no way to pick a subset of the numbers where the product equals exactly X and you're also guaranteed no number equals x because otherwise there's no way to win uh and you want to know the minimum number of bad segments you can make because obviously you can also just make end segments and then that would work um cool so this is actually again it's a greedy uh where you basically go make you start your segment at the beginning of the array and you go as far as you can until the segment becomes bad and you cut it off right before it becomes bad and then you just repeat that um the only thing that's tricky here is how do you determine whether the segment is bad or not um the way I do that is I just basically I just it's like a DP on the factors of x I just determine which factors of X we can create as a product and then once we do hit X we have to break it off um so I did this this is maybe a little bit faster performance- wise but it takes a little longer to code I have a c i c up to 200,000 and then factorize X I find all the factors of X um there are most 128 and then I just go through and I just do this DP so basically I try multiplying the factor that already works with my current number a see if that produces a product that is also a factor of X and if so set that thing to True um in retrospective I realize this is probably probably not the ideal implementation in terms of like finishing quickly I actually think okay let's let's regret it I think it would be better to just do a set so it's going to be slower for sure but that's okay I don't think that's a big problem so here we go so set in factors equals what I guess we could also do a vector maybe that' be good for type issue but just do that um cool and then yeah we'll [Music] sort swap I guess oops here and then if Factor back equals x if we have X this is this this should work this is much shorter code all right so I should have done this it's probably fast enough to well so take a while um yeah I guess you can also do this as a set that would also work lot of options here um let's try the set version I kind of like the vectors Vector version better personally yeah so that's not too slow that is slow that is slow so but you get a lot of time time so it's okay um what did know where his runtime was 93 okay he didn't use the set then interesting um anyway uh it doesn't matter he doesn't count so cool let's go to G Last Problem yeah so for G we're trying to add up the mech of B the the B+ one or like size of B Plus One Max of B for every subset B including the empty subset um they didn't make that very clear here but yes so turns out this actually pretty simple um you just iterate over the size of your set um actually could done this could just it from zero I think that should let's see itate over the size of your subset and then iterate over the mech that you're looking for now the mech is for sure at least this right so it's at least size plus one and it's also at most two * size plus one because at most sizes of the numbers are blocked so we can just iterate this and this and this is just n s um right here and then we just going count ways so this is actually pretty simple um the number of things less than Mech that you have to have picked is mexus size plus one because when Mex is size plus one you can't pick anything and when it's you know two * size plus one you have to pick all size to be less than x uh and then yeah in between same thing so we just do choose of xus one which is how many numbers we have but also we can't go more than n and pick those and then if we haven't picked everything we we need to choose the number we need to multiply the number of ways to choose size minus pick the remaining out of n minus X which is also the remaining number of options and that's your number of ways to do it uh and then multiply that by X and you're good so pretty simple and also of course Mex itself is never picked because it's the mech um so yeah that's it super simple um you just need a way to compute the choose functions and here just pasted that in my version so yeah that's it um yeah so I actually thought I actually thought G was pretty easy um easier than F but the uh it took me a little while to to get past the or the empty subset thing I actually had the my code outputting the answer minus one for every test case for a sec that was a bit fun but anyway cool um my contest and ni to post a video again after a while and it's been a while but anyway hope you enjoyed it and see you in the next one