Codeforces Hard | Algo & Coding Stream #9

actually exclusive or mutual disjoint and hello YouTube as well he will start recording just in case as I said a moment ago we were solving code versus heart problems today I will likely do the previous division one contest where I solved ABC and then the DF were very very hard problems hello Darksaber and our our treat arkad house containing nothing changed programmers can really live in home and work in home anyone here with 200 plus typing speed I doubt it will do will do contests does the plan I think Division one just need to move charts to the side they go to that to the other monitor so I could see what you're typing [Music] you I'm adjusting things bear with me for a moment how much they sleep I try to sleep eight nine hours a day it's healthy hello seeker four five this detect is this a good contest yes problems were interesting but the difficulty gap where was huge NBC was very easy and and the much harder will for D because I already spent an hour for dick I will my absolving will be about reading an editorial first also there is or maybe not I have an idea from my friend and I know it's an idea different from an editorial so maybe that will I will try that first and I fixed drawing tablet you see a lot of times when I streamed on Linux I couldn't draw properly because it was ugly with tablet they I liked proper drivers or something and now we'll see after it plugs in I will show you how it is different this will be biscuits just problem D see when I try to type let's say ABC this is how it looks this is my ABC I see because tablet is mapped into two monitors and so we have this space wait a second we have this space and it has ratio of a standard monitor so something like 3 to 3 to 2 but instead only this half is mapped into 1 monitor and this half is the other monitor and this makes everything twice wider but now I have a script I didn't manage to get it run automatically at the beginning of when I run my PC but I have this it looks like that apparently you need to off you don't see it you didn't see anything I'm stupid sorry you saw this right anyway everything is twice wider and now I have this script and when I run it oh no oh that's but it worked yesterday Wow trying to fix that let's try to fix that and then we will move to solving problems how did I get those names it was this may be that did it change a name stuyvesant eraser it's change the name when I restarted PC my tablet apparently changed the name will it work now well only for errors yes it did work let's try to draw something again now ABC ABC something still a bit different a little bit strange what is that okay something is wrong I'm only using half of my tablet just that second half of my tablet isn't working damn it have you tried open tablet driver I tried a lot I spent an hour on that I can search for open tablet driver because you see if I go to settings if I go to settings devices and welcome tablet it says nothing found no matter what happens even though I have drivers installed it understands that I can draw but I cannot change anything in settings because my PC thinks there is no tablet this is a hard cut versus problem maybe a sorry as a reminder general questions yeah I one more thing somebody told me that yesterday that I need to learn how to say a reminder and reminder how to pronounce puffs because I side them the same way I know that this is not something cut versus problems it's only a minute reminder reminder you remainder okay so as a reminder for you there are there are frequently asked questions in the description below video below the stream you can go there for questions like what I'm doing in my life or what's my age and if you have suggestions for my future YouTube videos then put them below my YouTube videos now if you suggest something even reasonable I'm not going to write it down now remember I'm doing something else during this string have you tracked this are our quickie page well I I for sure tried using this comment exit welcome it's it's strange to me that things worked yesterday though maybe I will reply maybe that will help didn't help how is it possible that the name changed that's bizarre to me then I'm it okay enough of this I I can write something still I have just half of space but maybe it's I don't know if it's Mia but it seems that I can do it slightly better now so let's work with that stage it drivers I don't want to do it now instead of doing catharsis so problem D do you have link in the description that I contest well you can open the last Division one contest but I guess I should put it in the description there is talk there is link to the contest that's enough then I will just put letter D here next to my face so people can binary search later oh and in chat if you want if you have some question to me at me say a director - how much do you make from YouTube directly from YouTube zero I don't have ads there is some number of biscuits h ii slime will choose a biscuit randomly uniformly among all biscuits and the owner of his biscuit will give it to random uniform player among the remaining players the game stops when one person has all the biscuits and we need to compute the expected time of end of the game i will i need to close that i don't want to worry about it now and is there a way to clear everything oh it is collaborative I didn't know it's collaborative or is it I thought that somebody type this what sir I don't know just create a new one leave yes hi it is collaborate if I didn't know that well could be worse you should make it private hmm interesting in and it's interesting that I used this tens of times hundreds of times could be worse I can imagine worse things drowned here okay normally on Windows I use OneNote can I use OneNote online i need to login i guess use that as well and so this I remember correctly I'm testing it's a bit white is there a way to choose dark background in OneNote for sure there won't be a way for that cut versus quantum programming contest I last time I didn't have time to to get into that but it seems interesting for sure how many problems have self after a contest it's about how much time I have 1v1 and with you when are you doing one before 1v1 and with who all will you compete against I don't know is good to be honest everything but is bad when my tablet doesn't work properly but I guess let's go with this slime and biscuits there are two ways to interpret this problem one is that let's go with sample test sample test is stupid let's say that one person has four biscuits one has zero one has two let's say this will be my kind of drug let's say that there are three people one has four biscuits one has zero one has to then either this can be an input or we can say that there are six biscuits and four of them belong to first player two of them belong to the third player this is equivalent representation and maybe one method will be better than the other and what is incorrect to do I try to do it during a contest even is to look at the single player now and every every second we take a random number in this sequence and we change it into another number for example we take this each has one and probability to be changed and we change it into an so one one simulation of this is to have this sequence of length let's say s and while not all the same is Rand module as size of the sequence the number of biscuits I think it was upper case as in the problem let's say as is the total number of biscuits and now we change owner of I is random another owner and if all the same of all the same then stop that's pseudocode for simulation of this all the same means that every biscuit has the same owner we are asked about the expected time of that and an incorrect approach is to focus on a single owner to look at this sequence for example look at this and think that okay right now it has four biscuits and we wonder when it will get down to zero or up to six if 6:10 we win if zero we lose but it's incorrect because you're doesn't mean I lose a loss and you don't know if from this you keep track of how many biscuits I have and how many other has so for example maybe there will be two comma something cover something it means I have two biscuits others have remain equals then if I lose both of those that I don't know if game ends because I don't know if the distribution is here is six zero or maybe two and four are free and furred so to keep track of just biscuits of one player it's not enough and instead can you explain problem please I think I've just did that reminds me of top coder finals I think top coder often has probability problems I don't know at cutter grant contests I I do a lot of at cutter absolving so there's that also there will be an issue that I cannot even iterate over every owner and for that simulates an takeno event but that's I first want n square working solution correct solution and then I will improve that okay now the idea is instead of keeping track of biscuits of one player this is idea by marching some leverage marching small uncut horses to say keep track what happens here is we take away a biscuit from somebody and give it to one other person first observation and this is one I had it's okay to say we change it it's okay to allow changing into the same hunter holder so if I take a look at this number and I say this should change into another number it's okay to say it changes into any number from one to three at the end multiplied answer by this because I can say that a few moves in a row they can be they can not change anything instead I'm computing the expected number of moves of any moves including those wasted moves and then actually maybe this they asked me to compute the number expected number of changes is that I in this new version I compute the expected number of all moves including changing a number to itself and then I know every one and number was wasted was was not a real move the second after taking a biscuit from somebody can I use cookie cookies easier world after taking a cookie from somebody don't give it back to anybody until the game can be done so if I have here the idea is if this player loses a cookie it will be free zero two and now I should say somebody should get this cookie but even if I assign this cookie the game will still not end so what about saying that I simulate this and only at this moment I've been taking cookies away taking cookies away and this moment this is a state that I can remember that this is kind of DP of free it will be it will represent a situation where only one player has cookies of possible situations it doesn't matter which one and now I'm giving cookies back so from initial situation I need to compute probability of getting into each of those I wonder about the first moment when only one player has cookies and then from this I will start giving cookies away and either I give cookie to this this person or or to one of the other ones and then the situation will be something like three three one zero doesn't matter if it's 0 1 or 1 0 and then I I get back to taking cookies away I don't need to assign that previous cookie immediately that's idea very much in school average well idea it is a working solution I just need to figure out the details later I will go with the editorial because the editorial describes something different I want to participate in culture of stack down I participate every year I even organized it once you're asking strange questions why won't you brush your teeth well I do brush brush my teeth let's say that the number of cookies is as uppercase s total number of cookies and is the number of players then from if that we have such a situation when only one player has cookies so from this DP of four I can either move to DP of three or I can move to DP of five no not the pure free because now I'm saying maybe this is already windows to unassigned cookies those two unassigned cookies they can be for this player and either this happens or this happens that one other player gets I cook now what will happen from DP of four one now I get back to taking cookies away from them because I know even if I assign unassigned cookies I will lose either this gave us a sec okay or this guy loses a cookie are one of unassigned cookies is also lost change into another unassigned cookies so possibilities are that's still DP for one when then DP of four zero so just the PFR when a single one is taken away and DP of free one we will have a ladder with there are two n States I wonder if we can do it's linearly for those two n states and now I need around there are four from far we can get to five from far we can get to further what come on right from four comma one we can get to itself when unassigned cookies changed or we can get back into four or we can get into free kamon from five will get to five one and from that back to five just like with for one we have this transition my drawings aren't really nice from this if we get to six living from far can I get two free no because if I have four then I decide about unassigned cookies there is free here we have that and so on that's the graph and now if that was a single ladder there is a linear way to the general this can be done with Gaussian elimination in cubic time that's terrible we don't want it most of the time a ladder can also be done in linear time with some freak generally if you just a sequence of states and from a state you can move the previous and next one that's easy and I have two options either to apply the same here or to get rid of those extra states maybe like those those on the right maybe those on the left seem easier because from for one we will change a color you don't want to drop files from for one you can get too far and either you will get back immediately or you will move to five and from five the fact that you will move like that it can only move you to itself or to five one or two anywhere else there is also this ending state six and then you could forget about the left part of the drunk from from free one also we can move to itself for one five one and I final State 6-6 shouldn't be erased I don't like this up in this drawing up his bed maybe I should increase the thickness move it around have you tried creates a drawing software open-source I don't want to try 10 10 things today there's this is there a zero comma one no there is no zero comma one like that and we had transitions from me to one state above or to any next state this pink annoys me like that also to myself and so on and 4/6 answer is zero this is not that how it is that way just there are two directions for six dancer is zero then for five if I say dancer for five is some kind of variable X can express four comma one in terms of that I can can i compute this probability of going from 3 1 to 6 well it came from the previous graph I think this will be a working solution what's the probability to go from 3 1 to 6 it will be some kind of interval it will be hard not to get in score maybe it's busier to compress into the left part let's think a moment I know it will be equivalent but maybe better because I have done normal states hiya Richter hello Chandra and guru good morning be puff okay what is probability of getting from three one to six or from two one two five one from 12 1 to 5 for some new color say green if there is free one then we assign one of unassigned cookies can I decide what cookie is that I can you know from free one what I do is I take away I take away one of the cookies after random so with probability if we forget about this the probability of getting to the same state maybe I shouldn't that this is but then I wish probably 1/4 we don't move like that we've probability 3/4 if one of those four cookies changes priority one for it's this one now prop from free we assign one of the cookies with probability one and we'll move down and yes always it's 1 and because we have one group one guy has free cookies and I want to give die cook and you cook it to him one hand one hand and every time there is an over and minus one to go to the right that seems reasonable okay I can work with that I can work with that expected value of time for free one or maybe let's work with probability from free one with probability I go up with probabilities preferred three four we move to stage the one with probability one fourth times something we move back to myself like that we go to the left and then to the right after moment now we go down from three to four this one ends and then right immediately that's a bad way to from free one to two to one with probability this to free one again with probability 1/4 times n minus 1 minus 1/2 probability I need to go to the left then down then to the right there is 1 and twice because I go down twice and finally to 6 with probability go to the left and then 3 times down but Papa hello welcome back stupid Internet but I hope at least that the video didn't break into two parts on YouTube that's one good thing about this I'm on I'm on Windows no the same thing happened as on Sunday week and a half ago my internet still worked but something is wrong with DNS settings I don't even know what is DNS but I know it's because of the illness and when I restarting internet didn't help I mean starting connection in settings of my computer then I were started router router and waited two minutes for that to do something I got internet back but obvious still couldn't reconnect I tried to restart OBS it crashed like it froze my whole PC what I clicked you're starting from button on my PC not on keyboard and then my computer started working again for a moment and I had seconds to save that file and I think I managed to do that where should it be I'm looking for that yeah I saved it us Opie's dot txt our pcs polish for description I have no this file this that's not lost but streaming on Linux is Spain India's just I don't know why I did and I need to do something we've saved the teddy someone save the Teddy please or because it's going to fall here the name domain name system here that's that because it happens to me that I can access only some websites some websites are not accessible I will continue doing that problem D ever since I changed my internet provider year-and-a-half ago it's strange it happens from time to time if I need this fing YouTube at least now I will be able to draw and when the same happened on previous Sunday I couldn't I lost ten minutes of writing my solution because I couldn't save this is a problem just a network issue I learned it last semester okay then please save it I mean please fix it there is a way involved in Windows and in Linux to change something about DNS and I tried that the worst thing about it is that is that when you change anything the only way to test this is to wait for 10 hours and say if ever it happens to you again not only some websites are accessible if I change anything now in settings for my for DNS on Linux I will not learn if that works or not unless it crashes again and usually it happens on the stream for some reason maybe because otherwise I'm using it like one or two websites I don't know reckon figure your DHCP I when I will be on Linux change your DNS settings in your rotor router maybe maybe I should do that but not now and now we are leaning on Windows on Windows those key things don't happen I think change or return but can be of the same company we have this fortunately I didn't lose that I lost the drawing but I can live with that you can change from Google DNS to open DNS and vice versa and I think I tried doing that already yeah I can draw so there is 6 5 comma 1 4 comma 1 3 1 2 1 1 1 and what happens from 1 1 I'm not sure and possible transitions were like that right yes from far one I can get to the next one myself our previous one and so on and what about from one one I guess from one one we can get to to one myself oh but also I can get to every next thing and that's from everything from everywhere but we've fixed probabilities that create a geometric progression so I will be able to pre-process that now what I was going to do next is just to start something I get a sequence I need to get to one of those states maybe also one allowed state will be a single one I'm not sure about that or maybe this will be my kind of minimal state what happens when there is two one when on inside unassign the cookie here it will get two one zero how is it possible to move from two one two one one it happened if I now unassigned cookie and it is one one now from one one if an unsigned unassigned cookie I will get into situation with one zero okay so it is some special situation and I know the answer for six and if I'm here the answer is zero and expected time to end from five one I don't know that but I will say that for five one it's X then using this X I will compute what's the expected time for every other state using that I will compute it here yeah I should get at the end some linear equation I hope it's not really the most standard way to use a trick I'm going to use if you use a Wi-Fi I don't use Wi-Fi so is there this text text should save D we've with dark do you see a character do you don't because it should be above okay the background I don't want background that's an ugly D what's up with this character I think it's not that sharp why text almost done you see this D is much nicer what's up with the previous one hey everything fine yeah this will not be nice to implement projects this is dated therapy let's call it cookies I can copy/paste my templates from somewhere submissions what about doing it first just for okay I said that I want extract that we'll be able to switch between double and modular operations let's call it m I think I miss fine name and for now we've disguised problems if you work with modular operations and something is wrong at the end you will get a stupid answer like random 9 random digits I start I want to work with double and then at the end before submitting switch people have that I'm sure that if I go to standings and to look at people in the top opening doesn't use templates but let's see here I'm looking for a class for module operations there is tracked modular I am looking for this this is a priority and class later we can monitor off base then we can use it just like an int anywhere here with subtraction multiplication and so on I want to be able to switch between double and modulo just like in the dated code I was looking a moment ago no pre-written class no protein class and here template of modulo does something hmmm I should spend a lot of time just in this to make it nice so what if now I just work with doubles for a moment given a sequence I would like to write a brute-force that for something that will simulate the process million times and will give me the average time so I would have some kind of brute force this will be just an input total sum of answers is 0 the sum of answer want the number of tries say hundred thousand times I try to simulate the process if somebody is near to the stream now you can go to this description for link to a contest and this is problem D from code versus too much too many things on my desk tries repeat not many times while not all same just a random index and change it to another thing in this range I also need weight that was not that the input is I want this to be a sequence of owners I think that will be easier to work with or not or we'd want to be so it won't be this is count cookie this is zero sum of the number of cookies as is now the number of cookies if I'm working first on first person and he has five cookies that many times [Music] repeat that many times owner pushback the owner will be sequence of who owns each cookie while not all same of I choose a random position and change it they of is round modulo the number of people but to do to a different number all same [Music] now I'm not changing a I'm changing owner acts different than owner of zero sales force what seems true there are moves plus plus I will count that number of moves trace it here I'm training some answers plus equal moves and trick turn everything that was below is a comment main that's for starters print let's just reading [Music] a was not declared because I'm interested in owner count cookies count copies sounds like a better name to 1 1 I got zero that's not a good answer this is 3 times 10 to minus 5 because I only want simulate this thing steady should say owner after I'm done I should assign the RI to the initial value otherwise it its ties to be all the same numbers I got to was the correct answer from the problem it's one because I have this I need to change the different number but I claim that some answers / tries that I need to add the end multiply by something [Music] that should do a job I got 1/4 to 1/2 I should get free free of course it's not that precise and for this I don't know what the answer is but we can see what program prints just followed you thank you if you look at the lead code my coding challenge or are we not interested at all I did Apryl challenge why is it so slow maybe it takes exponential time we have around 15 cookies what about doing this without too optimization I wonder what should be the expected time in this case apparently it's big what about just 1,000 tries it won't be bigger than total number of cookies right no no it is huge there are five people if every cookie gets to a random person the number of possibilities five is five to fifteen that will be expected timer roughly okay that's way too big what about just four one two three four even this is too slow for one two - one round thousand that's suspicious that's very suspicious it's hard for me to believe that I chose some test and the answer is so round and it's equal to my number of tries what are I was like can you quickly tell what you're doing in honor its owner of that cooking how long do you go in one practice session depends you can look at my past dreams sometimes it's six hours at cutter grant contest if not make a stream what's up with people suggesting that cutter grant contest is it today or something at cutter contests upcoming contest this Saturday 2:00 p.m. for me yeah I think I will participate yep or maybe not I have board games with friends this weekend but I think it's sounding I used to do in the past I could do more competitions but now sometimes I just don't have time let's fix this slightly let's say if repeat if this is zero someone starts by repeat now this estimates the answer button better for this input it's around 250,000 I could also slightly speed speed up this or right Gaussian elimination to exactly computed but I'm not going to this is just my brute force now every hundred iterations it will give me updated value it seems now stack that's suspicious maybe if it doesn't quickly win we've all cookies getting to a further four player then the situation is very bad let's let's try to understand that there's 250 thousand if I just make it like that is it much bigger now it's almost the same how could it be stack maybe I don't know okay let's take away cookies until only one player is remaining now forever player the probability that he is that last one to stand is I think like initial number of his cookies divided by all cookies again and let's call it count cookies this is probability if I take every next random cookie out of all s cookies then priority that you are the last one with cookies is this and then I also wonder how many cookies you will have or maybe I want a situation just before that because I operate with those with this let's like consider operating just with standard things like one two and so on maybe that's easier as an alternative because the full graph was not from one one I can obviously move to itself there's two one three one let's say that there are five cookies total what can happen from - one from - I need to now assign some cookie either it will be another player or this just like that from - one I need to take away a cookie either which will be one of other signs or it will be one of that first person with two cookies or it will be this cookie okay so we can move between those like that and the probability to move up is it's complicated because here we for some time have this well if we don't care about that it will be 2/3 and this is 1/3 then probability to move here up is 3/4 and this is 1/4 the product of those will nicely cancel maybe I can just move between those states so from free probability to move just down by 1 is 1 and Phi belief now otherwise I move right with probability and minus 1 over N and then stuff happens I can move to the left in Italy if probability this I can move to the left there is one for for that it's from free one eventually I moved yeah that's that's that but also this let's say from this guy there is an over these two to move to the right then 3/4 to move up and to move to the left it's 1/3 this times that it's 1/4 that's quite nice and now what's the probability to move all the way up here it's n minus 1 over n 3/4 times 2/3 times what's this 1/2 this cancels with that discusses with that it's again 1/4 so that would be extremely nice but all of that should sum up to 1 so something is wrong hater have you seen that problem I'm doing another problem I don't want to stop in the middle to think five minutes about something else I see that YouTube chat is talking about updating something on Windows where are we from why Windows Oh why windows because i streamed on linux half an hour ago and things went bad I started this dream from Linux if you watch the stream from the beginning where are we from there are frequently asked questions in the description below FAQ bug fix a Python program now I'm not doing that I made a mistake for sure should I make a big graph with all the probabilities just those numbers they don't sum up to one that's an issue they should if you wonder what should happen from some state and you can go to other states the sum of probabilities must sum up to one here it doesn't that this there should be one more one for from this we take one of unassigned cookies this is one hand and this is n minus one over N is now from this state either when I take away a cookie this with priority 3/4 or this now if one for the monkey for cookies and four for this free for for that plus there is but there is also some probability that we keep going here it's 1s it's something device something question mark divided by us but and unless that happens I need to count for that at the end but now I want to simply I want to simplify equations okay then from this there is 2/3 oh I see where it's wrong and this is 1/3 and now this is a special case where from this we always get down there we always one of those two no matter if I choose this or that and that was a mistake so to get to that last state it's too far because I wonder what's the priority of getting from here to here it's this times that times that times that if you multiply you will get this 2 / 4 beautiful - does that hold in general this probability will be n minus 1 over and then this will be 4/5 if I keep going to the left and down yet things will cancel the product of probabilities those will cancel or reduce whatever the name is at the end if I get here I will get 2 ok so this does work in general that's that's very nice now what about this or each of those states when they move from free like that to one for each of those states in between for some time I do those loops unnecessary moves that change nothing and I need to account for that when I say that this the expected value for this state it will be some some of this that and that and there's also myself then there are some extra costs the extra cost so into this when I move from five what should be multiplayer next to this number I will be stuck here possibly when I move from five to free or to 2 or 2/1 Nike now looking from this properties are related to one sixth when I was at free the probability to get hit back here was one fourth and four point four is too far of a deal here the probability of getting getting back here is one six one six one six one six one two six what if we think about Bernoulli distribution and binomial distribution yeah then what they described some particular process and I need to do a questions related to that process yes there are a lot of non distributions but how to say that maybe this knowing that distribution name doesn't help at all may-maybe there are indeed some tricks often related to one particular distribution but if you understand probability set expected values well you don't need to know them you will come up with them anyway so when I'm in this state then I will be here I will be stuck here with probability to 6 plus 1/6 plus 1/6 maybe I can write down a formula big found and white color what's the expected time when I'm in state five well it's one plus maybe not one plus some probability I go to the next state with probability 1 and plus otherwise times I wear heyis stop CV of 5 plus 1 6 x zv of 4 plus 1 6 times evey of two it should be roughly that those are probabilities to get to those states how many moves do I need to get there what if I say that every move back is related to muff one move forward at the end I need to be at the end I don't want to count those moves back what if I say that every move to the left isn't counted but move to the right is counted times two I think it will simplify stuff because then I can say with this probability I make two moves and then I'm in this state I'm in state with number six otherwise with this probability I will get back to myself or somewhere to the left now is for sure related to moving ones up and by up I mean from five to five one oh no no no they were assigning and an assigning cookies I should count only one of them maybe you will make a tutorial about interval tree on your main channel yeah maybe but this is not a good moment to suggest things because I will forget about that anyway suggest below my YouTube videos what I should cover go to my main channel suggest in the comments there I read comments and also other people can then vote if they agree with you it codes may challenge problem of the day it's pretty cool I'm not doing click of this month I did it every day previous month and now I want to train for Google cow jump around for result and this is why I'm mainly doing streams with heart problems because I focus on practicing are you going to solve a and f maybe maybe if I done with this infinite time so this is moving to right Iraq to right because moving to the left it means I'm assigning cookies ooh I don't even think this is necessary to be counted us plus one it's only count assigning cookies then when I move from five to five one so a step up should be counted step up should be counted steps right or up be counted because they are related to assigning cookies not I know signing and to the left I'm taking away that's not a move yet then this counts and move to the right and I will have one move up yes this is a move up moving to the left doesn't hurt shouldn't be counted I will anyway move to the right and the final thing is those wasted moves on this graph on this thing moving from free one back to free one there's some probability for that so some number of wasted moves it's reassigning cookies but again to none of those two people I might have made a huge mistake went 3-1 and other cookies are on the sign oh no oh no when it is free one then I'm taking away cookies and free and I get a cookie it might be given to that person everyone I'm taking away now everything is I I thought that it's all completely wrong I'm give I'm taking cookie away from this and that might be one of those undone science I don't know who that is okay it's fine now from from this side from the state probability of moving back like that is s minus 3 minus 1 over s that's the probability of wasting something this is s minus 1 1 over s probability of wasting a move now this I get to this state at all moving from 5 if anything any of those happens so that probability this happens I guess plus plus if probability to 6 I get some repetitions over here what what what it is for free for free it's for 6 the sum of red probabilities underlined in each of those if I get to those I am on this side ever times expected time wasted here because this is probability of wasting time that the reverse of that is the expected time I will waste here okay this far comes from three plus one over six six is and number five plus one this is my current thing so what if I transform this a little bit this is a constant five plus 1 is a constant because I'm in state five so this is 3 plus 1 over 6 minus 3 minus 1 times 6 when I'm at 5 this is for me a constant so I will say that it's this times the sum over that sum over that where this is some I for free it was true for for for it will give me 5 over Sandvik well it doesn't matter what exactly it gives just for which states I should do it I'm guessing up to 5 for 5 I'm still not dividing by yeah it's fine I think this is it and can I sum this quickly well sure I can pre-compute the prefix am scared sad thing is any miss any small mistake here any plus minus one and my solution will begin correct but I think that's the whole formula which problem is this problem D like you see next to my face here are resolving or explaining both what's shaking I don't know I don't know [Music] that's the important part cookies over us now the trick is usually by some variable X let's not mistake it with this by some variable X we denote expected value to finish starting from this state we know that expected value for as zero when one person gets all ice cookies the game is done this is expected time till the end expect the time till the end this is some unknown variable X if I now use this to say that evey of one is there is some probability to move again here and so on I will get from this that this is something times V of 1 plus something times if you have to and from this I will compute if you have to and but if I don't know if you have one but if your phone is some variable X let's say then I will get that a V of 1 if I have the equation like X is equal 5 times X plus 2 times V of 2 from this you will get a V of 2 is equal maybe minus 2/5 times X plus 7 this equation will give you X in terms it will give you if you have 2 in terms of X and I will express every next V in terms of X at the end I will have EVF s is equal for example 2 times X plus 10 and it's equal to 0 and from that I will get X does the trick so the receiving of 1 there is power I will just need perfect Sun there is that EVF I know that EVF 1 is equal 1 comma 0 this represents 1 times X plus 0 for every eye that's called me my state from 1 to s minus 1 I use the form I use the form from this I want to get Eevee of six actually so should I transform that a little bit this will move to the right to the left and this will move to the left maybe six maybe I should multiply both sides by L that's better than TV of six let's move it to the right side and this to the left side - Evi of six is this if you have five we'll get some special thing other things will not this time start okay let's do this I want to compute EDF me plus 1 in terms of X in terms of those parts first this term this now this is minus equal this should be a struct rulings it yeah this is a linear function something like five times X plus two you can add those it represents a times X plus B we have plus minus and a few other things that will be a good start there's also plus equal and minus equal and later I need to change all of that to module operators G minus equal what do I have n times if you have five so far so good does it compile I'm working what happens in the chart probably over Soviet already zpz what I solve this problem no I couldn't then spend so much time on that something is wrong with that result oh because I want this okay forget now days and then n minus one times whatever else we have I'll first this I will remove one from here and n minus 1 moves wreaths moved there it's N and is the number of people then it will be n minus 1 times everything in a was equal 8 times and minus 1 and because I have minus at the end I will do this compels doesn't return sure that's fine I didn't want that I'm just uncommenting for because it's easier to see right now I am done with that so just this Evy of AI x times 1 over and meet possible it's 1/6 if I call 1 and then it's too otherwise it's one here we have 2 6 and additionally we have this kind of free term that I plus equal times this constant now that's it I think it's like 5% probability that's everything here we'll be fine it's just a warning but let's get rid of that the return statement okay I compute a TV of that it's now print a V of s I'm not even writing that for now I don't use count cookies doesn't matter too much print brute force now I want to run solve quick tip if you post a screenshot of problem somewhere on the screen then it would great to cut the cut in the middle of the screen paste the screenshot of problem somewhere on the screen but the statement will take a big part of a screen if you want to make it readable in the description the rest inked a problem you can go and read that - infinity I am dividing by zero somewhere let's investigate all the division can i have division by zero here I guess I can okay okay s minus 1 minus I minus 1 and I just come from here since this what what was it before I transformed it three plus one okay it's this this this probability of getting to the same state this priority is 0 for this place for probability 0 the the expected time of this happening wait wait wait wait actually if this is probability I should say that 1 minus that the the yellow thing is probability of wasting a move if this is P then the formula for the format for wasted time is 1 over 1 minus P because 1 minus P is probability of success so it should be something else as - this one - P let's compute this it's as - I think it will be I plus 1 over s 1 minus P and now the inverse of that so as over I plus 1 this instead of that here I have what I had i me i is that right but did I have this was inverse of yellow so this is incorrect I need to change that and this is the prefix some seems about right this is me this is I this is I I can just and now instead of this inverse of yellow I should just have this oh this gets cancelled it just asked over me plus one for every eye no maybe 4-3 no those are reasonable numbers I got I know that EVF s is your expected time if already one person has all the cookies so I have this formula a times X plus B equals zero and I know I ain't be from this I will get that X is minus B over a minus B over a and using that I can compute real living for every state this is after the follow-up is done wait wait oh it was in correct place for every I is Evie of I I times X plus V of I be [Music] please be right otherwise I need to go for all the computations again nothing was printed that's about my debug thing don't don't worry about what I'm doing it just my strange templates my program claims that if the situation is 1 comma zero then the expected time is 0.75 to finish what shouldn't be below 1 if it's 1 0 and it assign but I'm not counting something well anyway it shouldn't be below 1 that's not right but I can compute the right value and see if my formulas are correct so what should be the right value assuming that now I'm allowing changing a number to itself are you going to participate in next up color Martin no I don't have time top color Martin's take too much time 0.75 what should be the answer if there are just two cookies if the situation is 1 & 1 & 0 and now I'm assigning a cookie and with probability 1/2 there's 2 0 and Taiwan the odd with probability 1/2 this cookie is like that and from this state I need to take away a cookie so for sure I will get to 1 comma 0 if we've probability 1/2 I win and we probably have I don't the expected time of repetitions of that is just to the probability 1/2 I mean in Italy with 1 for 5 win after 2 times and so on 1/8 1/16 now when do I count and move this is accounting a move plus 1 and this is counting a move then I believe my program should compute 1 because this is 0 that that's wasted time and I can check this maybe the drawing because this is less transformed maybe not that much here we have that TV of one the off on this half times one plus e V of 2 plus 1/2 times 1/2 times 1 plus a now what is a one six what is hot six I'm at one so it's 1/2 times me and that's it no for one I have this twice something ok seems reasonable the formula becomes with parity half I waste a move I use a move and win with probability 1/2 I use a move and get to the same situation ok let's make sure that if I say a veto is zero right I know it is 0 and when getting everyone is equal 1/2 times 1 plus 0 plus 1/2 times 1/2 plus if you have one what we will get from that is number one number one satisfy that no one equal all the cookies none of the cookies cookies cookies cookies er why did I put one here why dear please have this is what okay and now one is equal to half plus half of - no not right 0.75 I just compute let's just solve this eevee eevee of 1 times 1 minus 1/2 from the right is equal the 0.5 was automatically put here 1 note does computations have + what do we get from that if you have 1 is to 2 is equal 1/2 plus 1/2 times 3 yes yes if you have 1 is 4 and that's correct so let's also make sure that this gives us nothing because for six comma one now time no time is wasted let's remember that something is wrong with this one I bet that if I remove this part the program should be correct No this was that wasted time and here no time is wasted but it changed so it is incorrect in particular let's verify if what happens here is indeed the same if you have one is just I denote it as X and form equal to 1 I will compute it in terms of EB F 1 and if you have 0 I'm computing if you have me plus 1 and I had here I move this to the right so it's and I multiplied both sides by n right so it's this alone should work let's work with that multiply both sides by n move this to the right now get rid of this plus one but we have n minus 1 and minus 1 plus this is an okay now is this correctly used if you have me plus 1 this thing plus equal and that's that - equal movie of me times who put 5 here 5 is not a correct value to put here I don't know why it I had that but let's finish reading there is some I at the end I will add I multiplied by n minus 1 yes so I there's that iterate over everything and there is 1 over 6 1 over me plus 1 but for eveyone there is this special bigger number okay okay [Music] works if I uncomment this it stops working which means this is invalid I got free this formula should add zero in this case so let's review it I count for the twice that time as minus this I still think this is Val this is correct the yellow thing is correct this is probability of wasting a move one minus this is probability of success and one divided by that is his expected number of wasted moves 1 minus P will be free plus 1 over us I plus 1 over us but more final it also counts moving to the left yeah I should say this minus one or actually this minus one what about us I am NOT going to explain everything here it's basic expected value so that's at this correct now what about harder case is that correct how can I track that how can I get the answer from this if the input is 1 1 1 if the input is 1 2 then with probability 2/3 I will get to this state with probability 2/3 the input is 1/2 then this one will be eaten with 1/3 all right so if 1/3 I get to this state 1 first I get to this state otherwise to that one because it will be 1 1 and then 1 0 for sure then we claim here that the answer is 1/3 times this times that this should compute the answer for the whole problem and that would give us 10 point 6 plus this 14 over 3 [Music] but this is if we allow for changing a number to itself and if we don't allow that I think we need to multiply the answer by this by 2/3 what should be the answer the answer should be free I'm not having free here is the probability of player 1 getting all the cookies 1 over as - I want no it's not are you satisfied with your performance in couch and round - I was some like a monk maybe 5 or 10 fastest to solve ABC with a typo let's say in problem see this is why I didn't it didn't pass at the end so yeah I guess I just I made a mistake of going for the heart the heart was extremely hard problem and people who solved it knew something like that before and only two people solved it I should have went for the easy and then if I didn't make mistake for say I would have an amazing result an amazing place could convey but my final place is terrible but my performance wasn't that bad it seems that this is incorrect because I get here 2/3 it's something like that I'm slightly off I will get distance 2/3 what 28 over 9 this instead of 27 over line so something is wrong I can tell my program the first one to just say now let's run a brute-force first it will tell me the answer assuming that number can be changed to itself two one one should be - yes I got two two one two the answer should be six apart I think I'm nowhere near six I'm strictly below it and that's very strange I thought that I'm very close to the answer and because I tried to get the answer from the statement waitwhat x 2/3 how to forgot to first have n is equal to 2 and minus 1 over N is half not 2/3 so the answer in problem is free and so the bird first size twice that when allowing to change from a number to itself are you solving it with Monte Carlo yes my bird first is Monte Carlo and further questions like keyboard see FAQ you can write exclamation mark FAQ I think we need that we need a girlfriend girlfriend stream no thank you something is wrong something is wrong I need to just simulate the equations for [Music] for a sequel to free can I do anything else I can rate equation suppose I'll just make a full drawing for free for a sequel to free there is one there is one one two two one and three okay from from one we need to assign a copy there are two people probability 1/2 this happens with probability 1/2 this happens and then we get there and then we get there back with probability one it is sure but we can also do this here with one third with one first we waste a move so really here we move with probability 2/3 so 3.2 is expected time till we hit that minus 1/2 half is when we are at 1 1 I claim that this is wasted time expected value of wasted time at 1 1 will my formula work what was my final form oh this I plus one over me plus 1 this is 1 and now this is 3 over to 1.5 minus 1 yes this is half now let's write this equation and see what I should get you don't need my face for a moment and one is with probability 1/2 we get here the sweet probability 1/2 we get again there when do we make a move this is one move and this is one move plus V of 1 1 move to go up but also there is that wasted time this is wasted okay from this we will get EVF 1 is 1/2 plus 1/2 times e V of - I don't know that's better - right plus another half another 1/4 so in total it's free second 3/4 plus eveyone / - okay simplify that move eveyone to the right I guess 1/2 plus 3/4 is 5/4 multiply both sides by 2 we get easy of tow is - Evi of 1 dot EVF 1 minus 2/5 and let's see if my program agrees because I can print not only that also this it computed easy to ask 1 and minus 2 not minus 2.5 something went wrong unless my computations are wrong my program computed a veto as V 1 times 1 minus 2 point 0 that free term is incorrect let's again follow the free term here it's with probability 1/2 I move forward this is one step if otherwise with probability 1/2 we make step up we waste some time and then this is in total free 1.5 times 1/2 I will multiply both sides by 1/2 so this will be cancelled this will be 2 times that and now I have 1 plus V 2 plus 1.5 so if we took plus 2.5 it should be 2.5 something is wrong in count and int incorrectly it in correctly computes too so let's follow everything related to a free turn giving of 0 doesn't have a fritter I have this and what is another place of return this the sum over 2 over 2 so 1 times 3 over 2 is 1/2 this is half the total is half but a gets multiplied at the end by 1 so nothing changes we see a half from here and one from there I'm saying here 1.5 again if you have I if you have one doesn't have a fritter it's just X Tim POS computed as zero 3 over 2 y as over this should be freed second minus 1 I have wasting p0 distributable and also also okay maybe maybe this will work - 2.5 and you know what else I wanted now 66.5 I get and four is that correct I claim my program things that we get here with probability 2/3 if I remember correctly and otherwise this right now my program thinks the parallel 2 is 2 times this 1313 over 317 over 3 5.66 I got I'm closer well this was fine now let's compute the next term I guess let's see maybe I have another mistake like that why did they put brackets here oh because of minus 1 this is double I don't need to cast ok I'm getting close I hope is that bad that I'm wasting two hours for this now the same for a 2 I wonder how much people benefit from such a string from to will reveal a number if probability 1/2 it's this person and I won with otherwise we get here there is no time wasted right here then either we take away one of the numbers one of cookies with 1/3 it's this otherwise we have to furred it's that there is no wasted time here and from one one one we do waste I think it was half yeah why is that it's half but eventually we will go down with probability one and we'll get there I claim that we should get you have to is with half we finish the sweep priority half it's either we go back immediately so actually it's 1/6 times if you have to because we go up and then down otherwise we move to the left so with probability 1/2 times 2/3 1/3 but it's still wasted I move with 1/3 we move there it's also just one move yes it's one move because I only move count moves up and right other things are just counters to that one plus this is expected twice the time at one one a severe fall and I know by the way that if you of one is something already well it's ax let's now simplify this Evy of 2 is half does this give you a free zero I can skip that completely 1/2 times 1/6 plus this plus three second times that is just half I will combine those half and half it's one and we have we are getting something nice five six times if we of two is equal 7 6 times 1/3 times that times 6 over 5 times 6 over 5 I got this this is one point four plus one point four what did my problem get instead it got this every term is completely wrong computer TV to us X minus 6.5 now wait wait I'm should look at this should I I'm stupid from all of that I should completely via free they used us to compute a via free incorrectly cut rate of that let's multiply both sides by six by six or maybe right - I'm not sure this is seven six is that right we will have 1/2 plus 1/6 does this have in it ok how to I will move Evy furry to the left and it turns out to be that right if I move to the left it should be with mines or just let's move everything from right to left then to the five six times Evie of - - seven six - multiply everything times two and we get that what was iffy - I don't remember anymore if Ito is x minus two point five X minus two point five X minus two point five do we get something very ugly not really actually axis indeed just X 5/3 minus 2/3 will be a single X then minus 25 36 minus 7/3 so this is 14 third 14 6 so 11 6 and what did I really get too many windows no completely different number this is 13 over 2 minus 14 over 2 and what now what now can you advise what is a good place to start learning watch my video for that with PeopleSoft use this same strategy I don't know titin simple Python simp I can simplify long equations some infinite sums and so on I'm using C++ also if you're good in math you should be able to do all of that yourself now the stream is two and a half hours but that's a bit too long for solving this problem I guess I need to find that discrepancy between this and my count let's see if my couch seems to agree with values from this graph move this to the side not TMP what about why am i all the time closing this what is TMP 1/3 it should be going up this is incorrect TMP using crack going up is half moving to the left is 2/3 so the product is 1/3 times the wasted time something is wrong with tamping yeah I plus 1 for I equal to 2 this is 1 this is 0 correct but for I equal to 1 the wasted time here is 3 over 2 minus 1 this is 1/2 but what about this 2/3 that's not to further because wait it is to firt no it is should be going up is half going to the left is 2/3 the product of that is 1/3 why I plus one maybe I made some incorrect observation earlier so getting here is 2 over 4 n minus 1 times and since I that I'm forgetting this term is that possible the probability that I will waste time here should be this times that and right now this corresponds to I plus 1 over me plus 1 this times that will be I plus 1 over me plus 1 is what about this little thing but it worked before for non 0 TMP this TMP was right how was it right going up was the only possibility going up was no it wasn't happy oh but I added done with this probability and minus one so we had n minus one over N to go up and minus one over N to go up and I'm using that here is let's remember part of this thing where I multiplied both sides by n to get rid of one over and in a lot of places it was 1 over N 1 over N is just if I go up what happens after that it is correct is it TMP is 1/3 let's look at the drawing after I go up then it's 2/3 times that it is 1/3 it is correct okay let's check other values I'm at to iterate over things from one to two and to a expected value of one times 2/3 there's two first to get to one that is right for 2 it will be 1 over 3 1 4 to go down this is also right I will add a view of this that probability is that help our variable for what happens after I move up and this happens with probability 1 second I have other than that we have this Tempe was computed correctly to a I add this TMP thing I can print I but I don't see what it should give me I'm running this so many times that it would be really useful to be on Linux there I work with council with wake that the big terminal OneNote for drawing question mark yes OneNote for drawing when will you start the next question if I always knew how much it would take me to solve a problem this is I whatever was completed to say well Evie of one you have to Ivica of towards this and I checked that it made sense then I should be with probability 1/3 I go down so I get to this plus with probability 2/3 I get to that so X plus 1/4 of that plus 2/3 of that is 1 in total so it just X and then 1/3 of this is minus 5 over 2 minus 6 over 2 for now I claim it should be minus 6 over 2 which is minus 3 why it isn't I would check quickly if this everything is fine here B - a - B - B I be adding subtracting yes that's suspicious did I compute it incorrectly this is what I yes I I did something stupid was this big here before Oh earlier I just printed that it is this times 1/3 minus 5 over 2 minus 5 over 6 okay this is minus 5 over 6 and I add TMP the MPS expect the time of being wasted here and it's this times probability of getting there so 1/3 / 3 h DM p if we add that it's indeed that when 0.5 I think is fine then how do we use I do we you say well from - from - we will get two free or with probability 1/6 what about this with priority have I get to a and I no way because I is X minus half and if E - I also know it's this question mark I want to compete question mark is X minus 1/2 plus 1 it will be X plus 1/2 multiplied both sides by 2 and what is question mark x minus five minus one minus six point five damn it damn it and from this if this must be equal to zero we get what is X and it turns out that this six point five this is 4 this is zero and we indeed start with 1/3 we get to this tight otherwise we get to that side and this doesn't give me a correct answer come here something is wrong with my equations my logic I don't know what problem are you talking about problem D from contest cat versus contest where link is in the description it's a hard problem and time solving it now for two hours over 2 hours I didn't want it to make a long stream today so I think this will be the only problem for today but I want to finish it I need to look for a mistake let's try to be careful there are two people one of them is has two cookies and there is also one unassigned cookie assigning a cookie costs one more either this unassigned cookie it went to this person and he done got free or otherwise we get to this situation and I wonder what is the probability to finish starting from two one actually I know this probably because it is computed by for example my word for it is six six point zero I can write it down zero here six point zero there so from this if assigning costs one operation and being here into the end will have four either we finish or we do that but first we make an operation of doing that sure then I wonder what it should be here from six zero either I move down and it doesn't cost I take away a cookie I take away a cookie which doesn't cost me anything with the probability 2/3 I get to this tight can I claim that 6 is equal to 2/3 times X plus 1/3 times 4 where X is the answer for this place if yes then I can compute X X will be 7 right 2 times 14 for 18 years this is 7 and finally from 1 1 I now assign a cookie I take away a cookie which doesn't cost me anything I take away a cookie but in tell me that one last hidden cookie with probability 1/3 I'm wasting a move so with probability 1/3 I took away that thing I'm not sure about what to put here it's some cost some cost see I'm not sure what this cost should be plus 7 again this probability we get here otherwise with deferred dothard what happens is we get to this again let's denote this by X right now and from that I will compute X but what is C what is that cost for me I say that assigning a cookie takes some cost but this unassigned cookie I can imagine for a single moment it gets to one of the other one of two people and that it's immediately taken away also I could say that if I assign this cookie then I just get this situation with cost one I can move like that all that makes sense seven and six are fine because when I'm here I can say let's assign this cookie the situation is to one so I'm here that's fine I think that C should be one taking away that not assigned cookie and assigning it for a second to somebody and taking it away and then what we will have seven is 1/3 times 8 plus 2/3 times X then X is 6.5 well I think it works 13 plus 8 21 over 4 is 6 okay so maybe my program is correct from 1 what will happen I sign a cookie of cost of one either I will move to the right with probability 1/2 but it's a right person or with probability 1/2 I go there it's the average of that ok this is a correct value 6.5 is the correct value and 4 is a correct value everything here was computed fine my program is correct but how to get an answer from that we start with 1/2 this is right in this graph there's answer it is here this is initial state but I claim that in more general case I have just two n state and the initial one isn't one of drawn States i I want to use those three values to compute it and I said that there is probability 1/3 that I will get to - oh there's probability 1/3 that I get to this one and to further that I will get to this but before I get to this I will waste some more moves ok my program is correct I didn't know how to use the answers I computed real evey now I have some initial state like this is maybe the input but what I know is if one person has four cookies and the others don't have anything and other cookies are unassigned yet I took them away from somebody then I know what will be the answer from this I just need to move to some state like that for example zero zero four zero yes this is possible I guess because we can give it no we don't give anything to anybody we just take things away and on the side okay after I take one cookie after I take for example this cookie then from now there is probability 1 as to waste a move after I take another cookie there is this probability to waste a move wasting a move means that the next cookie to tag is unassigned one east waste a move the end when I get to this we've small sum of numbers being here for a moment earlier there was some probability like this to waste a move it's big from this one is a moment ago it was like that and there was this probability to waste a move I need to sum up time wasted from dogs and again if if P is probability of wasting move then one over P is probability of success 1 over 1 minus P wait expected time to wait for success - 1 is wasted news I already used this formula it is it is it is here 918 yellow pink on one of the drugs I will need to sum this up but also I need probability together those are mutually exclusive if I get here it means I will not get this is exclusive with getting to this state so for each of them if I want to reach this I just care about the number of first elements if I have five red five red balls and here it's what eight blue balls every time take a random ball what's the probability to have exactly four red balls when we are out take the last blue ball I think I need to solve this problem now I focus on this person and I wonder what's the probability that I first take away cookies from all other people I want to get to the first situation when only one person has assigned cookies and there are some unassigned cookies as well and this should be easy this should be easy some binomial coefficients but this should be the first such moment I don't want to use inclusion exclusion because I'm weak with that [Music] I guess I want to say let's go with more general case that there are six red balls and I want to farad was to be at the end then a moment before that there were four red and one blue the number of ways to achieve that is among six red balls choose four times those are penomet binomial coefficients out of eight blue balls through seven this is a number of ways to get that this divided by among all four six plus eight choose four plus seven that's the probability to get to exactly this and now multiply it by 1 over 5 to take away that last blue ball that's the probability to get to four red zero blow for the first time I think let's see to it if it works for our to come o on what's the probability to get to one red one blue one red zero blue well a moment before that there must be one red one blue the probability to that is choose among turret just one red times among one blue to 0 so 1 divided by this this is 2/3 and then among those I need to take away blue and this is equal to 2/3 times one second Alfred I came this is priority to end up in this state there is also some probability there is one first that I will end up with to rat and to one that I will end up with one blow okay I think that's fine that's right let's try this need binomial coefficients work in progress for now it's just a small all right later I will anyway use modulo I will iterate over every person I'm back for every person iterate over how many I want him to have at the end when others get zero for the first time in remaining there is what count cookies what's the probability for that the probability is among his cookies I want to trust the remaining ones times among cookies by other people to create a variable because it's too long focus of other people I want to trust everything but one times the last one and so this is one over s plus one with this probability we get to the situation this is almost correct what it doesn't count is that wasted time before that first situation happens but I should get answer slightly smaller than six I think five point eight or something that's twice too big [Music] what do we have for the first person there is probability one that will get to this situation that's not right it shouldn't be one it should be much smaller so it's oh I didn't divide I didn't divide by this among us we chose his plus one that was supposed to be slightly smaller than six okay who is one sister I wanted to print remaining not stressed and also this should be remaining so this is initial his among distrust that money monk remaining trust one total trust remaining plus 1 and divided by this now it will be it will be 5.8 you'll see 5.8 know something like that just now wasted time it's yeah it's this you need to use this the last one is that when forests remaining combine this with this formula extra is Europe 1 over s this will be last from I equal to 1 to this P waste is I over s and extra plus equal 1 over 1 minus P waste minus 1 and now let's hope to see exactly 6 please pretty please not 1 6 - is correct now what about thirteen point five this is also 13 point 5 4 4444 I think we're done with quadratic solution I for a moment it's cubic here but doesn't matter too much and I need to to remaining parts well one obvious one is to do this twenty-nine I guess good enough point - it's not that precise but also I would expect to be closer to the answer so let's do that million times that's a bit suspicious okay it got closer to twenty nine point three three one more test of the ones let's do more seventy will this converge to seventy I could also take somebody Scout that might be a good thing to do that's not seventy don't tell me that my code is wrong well well dammit that's terrible I have no idea where the mistake is drink just a thousand get rid of this maybe not even run brute force I will compare with somebody scout right after somebody told me how to date roughly I spent down three hours after that I have quadratic solution that doesn't even work feels bad yeah it does that's a shorter solution we bounced too much equations right but that's not the point to rewrite somebody's solution custom test this was the output for one one two oh I mean what am I supposed to do with that the Finks model this is 29 plus 1/3 so 87 88 over free 88 over free that what if he prints this x free while we get 88 yes my answer is correct here what if we do that 17 it is 70 okay okay okay what's the reason for that maybe with taking value model of for maybe runt is not precise enough and value model for is very it has some cycle what's the most amount of hours you are able to practice programming problems today I participated in some 24 hour contest it happened to me to spend 22 hours solving problems in in 22 hours among 24 let's say with some short short sleep break and talking with friends maybe 20 hours and don't do that my solution is fine now let's try to spin it up let's try to speed it up first I don't want to run both versatile yes English in the chat please - seven - is that an integer that's surprising that's not integer does it midnight my answer is better or maybe I'm not printing it precisely enough what about that this is that said precision xx fixed okay it seems to be let's print it x free [Music] eight one eight four ten a 2814 what do we have here eight one eight four okay this is a correct code now let's get rid of that no no no first part let's try to slowly get rid of some for loops every time I will print this and this multiplied by three Evie of I we have prefix Sam after me let's keep track of that son do this evey prep some times 1 over meatless wound but there is especially I add the first one again the easy of 0 I messed up I messed up why is it not equivalent give me a sum up up to me Evy of 1 this is the special case not a way of 0 eight one eight four ten correct okay one part is done now this you know how can I transform that there is a constant as over me plus one otherwise it is something easy though it's not a constant but for sure it will be easy to do this is just related to I me plus one is constant but if I just do TMP plus equal TPMS equal to preferential the traffic sum of ratio the moment earlier without this one times this denied entry needs discussed right [Music] don't declare because this should be me say it's nice to first the quadratic solution and then just take take a look at every next for loop and optimize it eight one eight Thornton this is linear there is not nothing inside the for-loop second part they need to do this faster and that will not be easy I think I need to understand what happens under the hood I have a cube exertion this this is trivial for sure but not that the people ever implement a segment three four perfect some solutions in contests if they don't think that my beat happens once every hundred times do you have a repeat problems to understand or do you keep solving new ones if I solve a problem then it means I understand it and I will understand it in the future maybe I will forget the details but I'm not redoing the same problems though don't you surround in C++ sure but answering to drove truth I'm doing that locally I'm not going to submit that but indeed I should use better generator to avoid that precision thing if I repeat a lot of times how long do you think it will take for a beginner to win a cut versus round infinite time 99.999% of people will not win a cut versus round and for those who win you can check when they started and you have the answer okay I stated this problem here we have some number of red and blue balls every time take a random ball what is the probability to have exactly for it it isn't that bad because the this iteration even though those are tougher loops I turn it over up to the number in the input the sum of numbers in the input is 300,000 so this combined with that it is linear just iterate over every cookie once so it tastes enough to optimize this and that should be easy be waste and this is trivial right as remaining just a prefix perfect some of wasted time and as minus one I believe it's enough then this is just proof waste extra what is extra come on correct okay so I explained why it's linear even though there are two for loops what's left I need to get rid of that so instead of this I need a function first let's do it with doubles factorial for I'm divided by this when we have solve [Music] [Music] up to us that was not the easiest solution for this problem for sure especially if you look at length of code by omnec but I'm proud of myself well I will be after I'm done correct and now everything should be linear so what's left is to change everything into computations modulo all of that that's a lot of comments well most of it happens here inside is it a good time to create a struct maybe maybe not brute force I don't need you I mentioned earlier distract for model operations but it will be able to we can add that subtract print and so on I will save it and later maybe work with discount again so this is projects cookies double but now let's change things because in the problem they give us a model and I need to implement a lot of things I turn custard too long long items model amount power power is needed for modular inverse [Music] [Music] [Music] now I need to use it everywhere I hope I won't get time limit exceeded because although all of those operations are quite slow modulo operator is quite slow [Music] as you see it's quite annoying and this is why I need a fast-tracked for that [Music] somebody knows this is a mistake what I'm doing then please tell me that will be very nice of you here this is L by an so it's fine what do we have here it's inverse of that again if you perfect some this is also this times is fine raesha prep some is al but this is not so multiplication of me plus 1 and division subtraction of division and Taiwan I need itself I will add that at the end do you feel excited I might get accepted in like three minutes itself doesn't exist this is also it's fine this is also it's fine - one this should be actually minus 1 is minus 1 everywhere anywhere else no this is mind if first more minus 1 by that almost there if you notice a mistake though let me know in which line the universe of this and subtract one it's so easy to make a mistake here multiplicate dosto / that Fang and / this last thing remaining is small so I don't need an extra finger divided in writing my divide because divided is a keyword or something I don't know what's wrong what's the probability that this will work zero that's the probability maybe not what what is the answer seems like I'm three times to long six is six correct Oh times n minus 1 over N free free free zero two zero nine two one nine two one yes this is some very special case maybe first this is general one should be eight zero one eight zero one blahblah zero nine zero to nine zero tonight okay now do I need to make an if isn't programming beautiful once you get things done if something if everything belongs to one person already then we're done everything is equal to s then do this what did I do wrong cannot open output file cookies X permission denied who hacked my computer perfect opera star keep going thank you think don't you eat do it every three hours why I cannot compile I can no maybe the exact file was still running I think that's the case please please pretty please where do you work see frequently asked questions what time is it where you live 1:00 p.m. accepted I spent one hour on this problem during a contest the traditional over three hours well I think we will soon finish this dream I guess I should written a tutorial and learn a proper method today also I can take a look at code by March in school average to see if he did it in an easier way my coat seems terrible but it might be related to the fact that I have a lot of comments and not sure about that let's try to create a new file save it as cookies clean and is that really that long and ugly nothing here should really be counted because everything can be one line the one line I will collapse that and templates don't matter then what do I have here 143 from 88 60 lines 5550 like five lines of actual code that's counted as 50 verses here this would be 60 including debugging lines well my fing 54 okay I can compare that I guess visually this is my 54 quite long lines here close to the bottom maybe the the last part can be done without binomial coefficients he does he pre compute them yes he has factorials she'll is polished shinny is polished for factorial he also has inverse of factorial uses that and he has a function for binomial coefficients it's called DeVoe uses it twice it might be the same I will talk later with him to learn if he did this everything the same way that's cookie screen screen can submit that again but there's also editorial and editorial describes completely different solution looking at the chart um Nick has such a clean solution I think editorials describes something easy and it might be just equivalent see yeah did this this is easy that's the whole solution of course discounted ugly organizers of contest should be allowed should be forbidden from putting something like this in an editorial with some random names but this is a solution for that I need to read this I just don't know if I will do it now or maybe later I think lighter because it's good time for me to grab a lunch so let's finish I also have some other things to do today this stream wasn't cut versus card problems it was just a single heart problem but hey I'm happy it worked at the end I spent way too much time on that way too much next time maybe Sunday evening Sunday evening is my next stream and the possible thing to do is create those that's tracked for model operators and printing real values because it's bad that it took me time to switch and I could make mistakes that way I should in five seconds be able to switch between printing real values and modular operations especially there is such a non trivial code it would be bad to miss something up anything in the chart is it which talks about Java okay so that would be everything I don't see any questions recently in the chat thank you everybody for watching with me and see watching me and think how I struggle with this not really easy problem that's the solution the thing I implemented today it wasn't my idea somebody after account has told me hey I got this idea and then I after after a contest he managed to get that accepted and now for some reason I struggled for a few hours I don't know if that was because I was dreaming if I I'm not weak with such problems usually I do them and I should go for all those equations computations quickly maybe it's because I didn't have pie in pen and paper and with that I would be much faster I wouldn't jump between drawings I would have working in front of me the whole time also in the drawings I kept modifying some equation during a contest I rarely put so much so much comments in the code I will do that on a piece of paper and then I can go through that again I don't know it would be less chaotic would it take me then last time and there were some mistakes that could be avoided we were strapped somewhere I didn't cast to double I changed into something else and then I had as / I plus one without casting to double so it was surrounded I wasted half an hour for that how to module of billion seven the same way you use any other model what do you normally grab for lunch what what all people import it you can write in you can like guess search in Google what people eat in Poland but for example burger and pizza are fine okay thanks everybody for watching again subscribe to the channel to the main one Arita see you Sunday evening the schedule is in particular on twitch when I downstream so see ya thanks for watching

Channel: Errichto 2

Views: 48,995

Keywords: programming, coding, errichto, codeforces, algorithms, competitive programming, atcoder

Id: I7wrUyuCfSY

Length: 223min 9sec (13389 seconds)

Published: Tue May 19 2020