George Hotz | Programming | HackerRank warm up LETS GO | Educational Game

Key Takeaways

buy them I'm going to be upset I'm never going to stream again so that's my call to action uh for you guys when it's time if you want to see great content uh like you know what's about to go down right now I've never actually I don't even really know what this website is um hi Clapper s welcome to my chat room uh yeah we're going to Yo good morning good morning it's almost 9:00 we're going to play a little hacker rank I've never played played this before I think I know what it is but I didn't do my research because I'm a shit tier streamer um but all I'm saying is when I sell you guys T-shirts if you guys don't even buy 36 t-shirts that's it I'm done streaming I'm quitting the internet I'm going to live in a mon Monastery that's the one where you make monks at Age of Empires you know H 100 gold bro 100 go all right let's go let's go all right what do we got to do oh hint oh I love when they give me hint oh type return a plus b oh boom I'm a genius let's go this is slow no it costs 100 gold to make a monk oh wow they're really my student or professional I don't know man I'm always a student that's right no I'm a professional how many years of experience do I have God I don't know know I think I have down not many that's right all right um continue practice oh I can unlock a badge if I solve more problems okay oh my God this looks hard what do I have to do compare triplets it created one problem for hacker triplets blah blah blah blah blah oh wait this is a joke really so it's like this then which way was the less then Alice receives a point if a is greater than zero so if x greater than y r Sub 0 plus equal 1 LF Al less than y red is that right go oh I shouldn't have just submitted it oh but I'm a genius that's right that's right we got on the first try all right next challenge let's go let's go let's go let's go all right how we doing boys how we doing all right we got to move the webcam is that what I'm hearing we got to move it all right no no no no no don't move that no that's wrong that's better oh boys boys we just beasted some shit all right I must return a sum of all the elements wait this is a joke bro see this is why we use Python cuz I can just do that and we don't have to deal with bullshit about like numbers being the wrong size and shit CU we use Python let's go boom boom that's right first try that's right don't be a noob all right calculate the absolute difference between the sum of the diagonals right we take the left to right diagonal we subtract the left to right diagonal and we have to ABS them H what is an array oh it's like a god do I really have to write this all right um all right we'll just say like D1 equals that we'll say like D2 equals this oh yeah yeah buddy yeah you know if I did any thinking this could probably be a lot faster is that right I don't know man probably no no we messed up we messed up you guys got to subscribe to my shit um if you don't subscribe to my shit then you suck and we're not going to stream anymore oh I tyo oh it's ARR oh that was a dumb typo I should have tested my code oh that would have been so oh no we messed up no how are we messing up okay what we doing wrong all right uh don't get it I should be right two 02 Su across the primary diagonal some across the secondary diagonal take the absolute value and subtract them did I do something stupid oh uhoh uh oh 911 test cases failed uhoh can I make the text a little bigger sure for you bro are you a subscriber you got to subscribe if you want big text but I don't understand why it just works what did I do this is so stupid uh the absolute difference between the sum of the two Matrix diagonals okay I sum the two Matrix di to 02 1 one what take the absolute value of the difference run code oh they don't have to be 3x3 they can be biggy Matrix oh no do I have to write loopy oh not loopy oh that's so hard okay for I in length God range length ay wow we were so careless on this one boys we were careless that's right don't be careless is that right I think that's right I don't know we're just guessing this is a guess no oh no oh no boys we did it wrong oh God it's plus one am I off by one all right I'm getting real sick of this list index out of range um okay no we got to subtract one because zero won't work yeah yeah yeah yeah yeah blah blah blah BL blah you know what it's early it's early boys it's early right all right all right all right it's early yeah no no I know this stream sucks I'm sorry I'm sorry oh I heard a fucking star yeah buddy all right let's go can I change my camera position to bottom right you know what just for you bro did you subscribe this isn't the content you signed up for what you don't like my new programming come on we warm it up now the other thing we could maybe do today ah this is so hard you know what you know what no all of you ask for this shit in the comments All you ask the shit in the comments thank you Narco RL for subscribing you know I'm sick of all of you you know no no you know what no more stream no there too much haters in the comments too much haters no no there too much haters no only because we have a lot of subscribers but if I hear any more haters if I hear any more haters you're all done right who's going to who's going to kick the haters out that's right ban the haters that's right no no no no just yeah can we ban the haters no whoa who said I should develop a thick skin you're a subscriber you're allowed to say things like that all right um what no no no no no no don't tell me I'm fucking tired no you know what watch this shit watch this shit don't tell me I'm tired you see see you tell me I'm tired time out that's right that's right all right who else wants to be banned all right who else wants to be banned yeah thank you ABK for subscribing love when you subscribe cribe what's v. oh you want to be banned okay rther all right all right cool yeah congratulations enjoy your Fame all right you're banned all right cool get fucked all who's next thank you fox ubu thank you Ivy lions please subscribe you don't want to be banned well good you're not banned all right let's go um add a sub link and info I don't know how to do that I don't have Vim on this computer you want to be mod no you want to talk shit yeah you're a subscriber subscribers can talk some shit oh yeah all right all right let's go so you don't like Hacker News no everyone seems to like this look how many viewers we got we got so much viewers all right let's go oh shit what is this plus minus a decimal representing the fraction of positive numbers in the array zer um m okay this going to work all right now we're back on top that's right that's right now we're back on top who's talking about the clintons we have a rule in here it's no politics get banned all right who's sending me bits thank you for sending me bits congratulations you solved your fifth code challenge you know what you know what I'm just I'm in somebody Skinner box I'm I'm in somebody's Skinner box that's that's how I feel right now all right where's is there more codes next challenge let's go consider a staircase do these get hard or are these all stupid write a program that prints a staircase of size n oh I see and I have to make it have spaces wa this is a this is a joke you know what I'm probably going to do this wrong so I shouldn't shit talk too much for I in range I think so six actually has six so we'll just say print that's actually six all right let's go from 1 to n + 1 Let's print uh space time i - n + star time I is that right did I do that right oh oh you see you can't use you got to use hashtags not Stars this is for the Twitter generation what but they they did I print one no what it doesn't like my my new line can I not put a new line at the end is that the problem the last line must have zero spaces in it what it does wa I I don't know so these things don't look like these things this this is stupid I don't get it wrong answer because I did that okay okay okay okay okay okay guys like I don't know if I'm dumb but they look the same to me they really they look the same oh let's see my output I can't download my output it's a formatting issue this is just buggy crap F I'm disgusted no it's not just standard out flush it's not that I did I just do it wrong space [Music] um ow what's wrong but all right let's go all right all right all right all right all right all right is anyone talking sh is anyone being a hater cuz we ban haters around here we have zero we have a zero hater tolerance policy if I had a plate I'd break it to show how much we're going to break the haters that's right okay um what Su exactly the minimum and maximum value that can be some summing each of the four elements oh I have to be aware of something let's read uh do I have to be aware oh beware of integer overflow oh good point all right for I in range length AR RR uh sum AR minus a r r sub I equal a a equals that shit oh you know what let's use a list comprehension uh for H yeah we love list comprehension it's so comprehensible all right and now I have to return what print uh two space separated inures for the Min and the max all right let's go let's go boys let's go is that right yeah uh no we don't talk about open pilot in here you get one warning you get one warning go first semester programming all right oh I'm in charge of the cake no okay who gave me this job this is I'm not I can I can I Outsource this all right she blows out what return the number of candles what is she like short or something uh an array of integers representing candle Heights what your niece only blows out the tallest candles she'll only be able to blow out the tallest ones oh so basically you're telling me it's something like uh sum xal equals Max AR for x and AR is that right is that right that's Terri terrible code look at that that's N squared this is n s that's disgusting it's disgusting that you can write n squ code okay do these get hard ever or are these like for like you know the 90% of idiots that like couldn't pass like fizzbuzz that's kind of how it feels what I did it wrong what' I do oh is it too slow oh do I have wait how big can these be oh they oh oh they didn't like my N squared shit oh yeah all right want to see how we're going to fix this let's call Mar we're just going to say Mar yeah would it be nice if like languages were smart and could kind of do that all for you oh yeah didn't finish in time oh yeah got to not write n Square you see what I'm talking about oh yeah that's good that's good that's good that's smart all right cool is that people no all right oh oh this oh this is terrible all right right time [Music] conversion okay uh let's just say ready for some real hacks um H equal int s02 uh if S Sub 2 = p P MH + = 12 return uh o2d s per H uh is that right did I do it right yeah yeah good right let's start let's go yeah let's go let's go let's go oh no I did it bad all right what I do can it be like am or p.m huh oh we got to deal with like midnight shit uh yeah is there a good way to deal with this if this is not a misy compliant function you know because it has multiple exit points [Music] uh is there like a smart way to deal with that wow I prob did it wrong compilation error oh I forgot colons don't forget your colon I think you need oh what oh this is stupid is it that or that if it's a PM we do that and then that oh oh if I have five hackos I could unlock the test case oh my God all right is the font big enough for you guys yet make a circular array why is this shit wrong what I do that's never zero oh it's that's not right this one is a generic case oh there's subtlety oh H + equal 12 um if H not equal to 12 right cuz 12 actually stays the same and then what do we do if it's zero okay so um okay so otherwise it's am IFH = 12 H = 0 there we go oh you're a big fan oh thank you thank you thank you for mod 24 what do you mean by mod 24 oh I guess this could have been fixed by mod 24 and this is kind of just a bullshit rule yeah I I know I know I could have just summed mod 24 I I get it well no wait no I couldn't have no it's not mod 24 because 12 p.m. if I add 24 I end up with zero and that's not right whatever right are [Music] we no I have to like know what which one's though and I have to leave that alone oh this is just painful all right A B CDE e f g hi I range from range oh no but then this is Python 3 oh guys I'm kind of done how this is this is can these be hard can we find hard problems that aren't like bullshit H okay um a b c d e f g h j k l m o p q r s t u v WX y z a a equals that all right now we got to do K so it's a a sub K plus uh I could do it without mod guys watch how you do it without mod is that right raw 4 S 4 CNS if CN AA um return join rat if it's in the alphabet what we want to do is say aa. index C raw sub AA index C rat. append yeah don't do plus equals on the strings you know that's uh is that right no okay well it's wrong because else. [Music] aeny why did we get a q instead of a oh I got to deal with uppercase and lower case oh man um C dot if c do2 lower not equal to no but it's not even in AA at that point oh all right all right all right all right is python K sensitive for variables I legitimately do not know I could have just done a a.2 upper yeah I know I know you're probably over there in the comments right now talking about how I can do this much smarter but no it's wrong what I do oh I can ask my friends for help on social media what I do okay oh look at that oh oh all right all right all right all right who said I had to use mod um yeah that's right it is basically CTF code no I love things like this cuz it's I wish they were a little bit harder and I had to think a little bit more you know and not just like oh I forgot the string oh I got to do the string better oh I got two stars all right can I sell this account to somebody so they can like like go interview somewhere all right let's let's go find hard problems 99 points to next star let's try this oh these look hard 22 foolish prims okay all right this sounds hard hang got happy we're going to drink some tea because it's t o00 i be some mac all right let's go e okay next fall and champ thank you for subscribing to my channel you guys should all follow his example and subscribe to my channel let me know that you appreciate content like this ah okay wow I have to write my own reading code I don't need to if name equals main that's stupid I can just say like is that right I actually don't know I don't usually read things some though you while reading line something like this sorry about the noob junk guys I'm I'm a Noob everyone knows I'm a Noob but if you all like Noob don't subscribe but iFit what oh God got put parenthesis in the right order it's early it's early ah why am I splitting based on that okay okay okay abstracting agent thank you for for subscribing let's see what we have to do okay we we got we got to stop talking stupid because those other challenges were pretty stupid we got to start thinking thinking slow okay discs set of discs numbered one through R Place line random water what is a partial derangement permutation of an distinct none of the items is in its original ordered position if some not not necessarily all okay so if if one thing is out of position so so exactly K I'm not really understanding what natural positions are sh that given the constraints the answer can presented is a / B where A and B are co-prime positive integers and B is not equal to zero mod some wow this is okay well this is actually hard um how do we think about this number of non Prime discs and they want an exact number okay well so we're dealing with 10 million so we can't use n² stuff but we could use n log N Stuff well I don't even what is Q print the value of P * Q -1 but there's no other reference to q and is this the P they mean this is insanely hard all right you all wanted you all wanted I know I know what the minus one means but what's Q congrats for claim your reward control W you know what bad I know it's a medium right am I just stupid what what are p and Q let's see the original problem maybe they give you more okay well that seems more reasonable I know what what but but what are p and Q that's what I don't understand okay well maybe we can figure that out yeah yeah I'm looking at the example so somehow 89 / 315 gets you this which isn't clear to me like I understand the probability uh no I don't think Q is some shit for math I think I don't know like this problem just doesn't seem complete um okay so you're you're saying that A and B are p and Q and this is like a typo right a hacker an is kind this problem I don't think it's like like this is just wrong okay so let's say they actually want a * B -1 wow I have to do a modular inverse for this stuff I mean and I have to like type it in this little box I don't know I this is why I like project you look better I get to use like sage and gimpy and stuff I don't know if I can import gimpy um yeah I don't no I I get it um wow this this stream this stream changed fast into something that's hard okay uh so I mean I don't even know is there something built into Python 3 to do modular inverse yeah I know I can write the thing but the modulus is prime what oh P minus 2 that makes sense because of uh ul's little the little theorem is that Prime oh it's Prime nth smallest 10th digit prime okay so yeah we can just do that oh that's a cool identity you guys see the identity because I mean I believe so I believe if I say like B and - one and this should be one right yeah so that's one so if I subtract two here oh wow that's really cute identity all right see I love I love when I learn stuff okay so now if we say this should actually give me the right answer if we do a * T mod N I don't know how that all right good okay well at least now we understand what p and Q are and yes there is a bug in the problem text now we just have to figure out how to get a and b say the end code thing I don't know I mean maybe the way the whole thing works you actually have to do it o dark mode o no I don't like um okay exactly K prime number discs are found away from their natural position I I don't why why does it matter that they're Prime um let's read this this is exactly 22 prime number desks oh exactly K prime number discs okay so we probably have to know how many [Music] primes there are and then we want to work it out for exactly k i I don't know let's try that um yeah for some reason I don't think I can import senpai am I cheater no okay is it inclusive 1 through n so we want to say [Music] range uh so we'll just say capital P equals map is prime range all right so we'll print what what kind of is prime function is this never mind never mind I I thought the internet would be useful for something they weren't range uh do square root of n math. square root um if I mod n not equal to one false what are you guys posting about stuff stuff guys know things map object oh oh Python 3 and that was wrong anyway I'm going to do some float cannot be interpreters at integer thanks Broski so you only have to check up to the square root of things to see if numbers are prime okay I don't know why that returned zero if I mod n oh if n mod I don't get it twisted there's faster primality checks isn't there primes is in P guys oh no okay well so let let go okay so this five primes up to 10 so let's see that's 2 3 5 7 doesn't seem right I guess it's counting one as a prime if n less than two return false because those numbers ain't Prime yeah that not that thing's definitely counting one as a prime okay now that's four Prime sorry that makes sense okay X algorithm thank you for subscribing no I think look the answer is right because I hand coded A and B right like we have to figure out what A and B are so B is the denominator um what's the probability that we have a partial derangement okay so that's I think the partial derangement then is the denominator um is a complete derangement also a if some but not not necessarily all Ah that's just okay well so we have the numbers 1 through 10 how many ways could we possibly order them that's 10 factorial is this but see that even already might be a reduced fraction and 10 factorial I know it's 10 factorial but okay so then we do know that it's a partial derangement which means not everyone is in the correct order there's only one solution where everyone's in the correct order so it's n factorial minus one right um and then we want to know what's the probability that exactly K prime number discs are found away from their natural positions okay so I don't think we have K and we have P so we want P minus K to be in their correct position okay so P minus K diss total is n factorial minus1 P minus K diss in correct positions K diss in wrong [Music] positions so now I think yeah I think we can just say that uh is there python factorial function or do I have to write it def fact xal return x * fact x -1 um oh oh it has to terminate oh you always have to write the termination condition um and zero is a stupid thing so we'll say uh Bal fact n minus one I think that's right even though B there changes but that's because they just did the reduction okay cool is that right good my factorial function works that's like a prime number though I I don't know how is that Prime [Music] well yeah but that's never going to be 315 so maybe I did something wrong right but that is okay it could be a partial derangement does not include fold arrangement if some but not NE see this is what pisses me off about math it's like dude can you give me a real definition of this thing I don't know like it's just it's just it's just people saying words and the words some of them mean things and some of them don't it's cool like there's really good thought in there but like I don't know no I mean maybe this is just my complaint about their language I've always found like mathematical language kind of hard to approach like I don't know but then again it's not like I guess for me to properly criticize mathematical language I'd have to come up with a better way to talk about this stuff and I'm not really sure I have one okay what's the probability that we have a partial derangement such that exactly K prime number discs are found away from their natural positions what if it doesn't want to be a that what if it's a natural position W that's a whoa whoa whoa whoa whoa whoa whoa we don't do hacking on here Alex says I'm sorry I'm sorry and we people who suggest hacking it's no we don't do that anymore um this is what you want to be seeing thank you I would actually you know cril I really would I'd much rather read a formal definition um than to use the language and maybe maybe that is really the solution okay any number of nonprime discs may also be found in or out of their natural positions wait a second okay what's the probab oh okay no no no no no so this isn't minus one okay so the the minus one is wrong the total is just n factorial right because it just it the base rate's not that it's a partial derangement the partial derangement is is given so okay this thing should have a factor of 315 it does yes okay so now at least we can say that a is supposed to be 89 * that right so real a is that all right cool boom they follow that three 11 mod 3 is not equal to one so we conclude that 11 is not F gold [Laughter] gang did I write a bug are you making fun of me cuz I wrote a bug um did I write something stupid okay so we have B now we have to get n all now we have to get a um so exactly K prime number discs are found away from their natural position so that means yeah first off so this is right the only ones we care about are P minus K discs are in their correct positions Al this is just like an old this is just choose this isn't that hard if I remembered like eighth grade Algebra I'd know how to do this but sad point is I I don't okay so these ones in correct positions I think we can just ignore and then n minus p dis in any position all right so we we yeah take the coefficient of binomial distribution it's some crap like that right yeah if I remembered exactly what that was oh okay you're right you're right I told you I wrote some stupid fck how is the answer still right no now it's five five is not right um wait equals equals zero oh my God but we still get the right answer when we do all that stuff okay go gang thanks for finding the bug sorry it's early uh okay so we P minus K discs in correct positions so these we only have one choice for so let's place them first place them first no choices now these ones have to be in wrong positions so for each of those we get one less [Music] then yeah so it's like all right let's just write this stupidly we'll think about it later um okay so let's just say uh CN = n minus P minus K cn- = 1 a * equal uh CN minus1 not in correct position or I in range n minus p uh a * equals CN any remaining position all right so we're off by something yeah make sure that should be zero right so you have one out of end in correct order then you select K discs which you you will derange the formula for derangements is simply n/ e what's E I'm sure there is a simple way to think about this if I really just thought about it but let's let's first make sure I'm on the right track and and then we can go back and think about what it is natural log rounded to the closest integy I never trust things like that okay so you have them in the correct order and then you will select ones which you will derange no but it's a little bit wrong because these it's exactly right because but these these must be in wrong positions I think that's what I'm doing wrong here like that's what that's what I'm that's what I'm doing wrong here like this isn't correct um don't forget those cadis to prime numbers the prime number thing doesn't really [Music] matter um what the the only thing that the prime number thing tells you is what p is I think but this is wrong like you can't just say not in correct position because well why can't you the link to the problem it's project uler 239 but made generic uh yeah yeah imagination imagination you're a subscriber so I'm trying to listen to you but I don't know see I I never I don't know like I don't I don't I just it's hard for me to just trust that formula um God wish I do more combinatorics any remaining position okay that's definitely right for these ones no but sort of not because okay let's just take a hypothetical case where n minus p is greater than K if n minus p is greater than k then we can plug up all the prime holes with those right um all right let's look it up is this cheating leaves no element in its original Place yeah okay we have 1 three and six [Music] so yeah n subp is greater than K so I think the answer to this is actually just uh CN factorial it's not always the case no that's not right either okay so P minus K so K is three it tools permutations is fine but that's never going to I mean yeah we could write that I mean maybe it's not the worst idea but uh uh it's not going to I think these numbers have to be big right yeah iter tools permutations and gets big um okay so if we have three and we know there's four prime numbers that means three prime numbers have to be in the wrong place that means one has to be in the right place oh but okay it can be any of the one right so actually is the answer this times 4 no it's not right [Music] either oh combinatorics is hard you see okay the mistake that I'm making here and why this is actually smaller than the answer is that in this one I've already chosen the uh I've already chosen which prime has to be the Frozen one and it can actually be any of them all right who wants to write it with inter tools permutations just let's just make sure we understand the problem right fine uh it tools dot perations range n so that should make b equal to the same value I believe yeah that's right okay now let's test to see if it's true so we need P minus K uh discs in the right position K discs in the wrong position okay so we want to know the prime ones um for let's say n for I in P if is prime I uh this isn't exactly right we want to say not just P but we want to say a new umate p c pause W pause if is prime I so we only care about the primes if pause equals equals i c pause plus equals 1 else uh W pause plus equal 1 if C pause = equal p- K and walal K A plus = 1 is that right if I was on Windows we could run this all locally uh oh well that's too bad uh yeah the I know the problem's not Python 3 uh no yeah we memoized this PR but didn't fix it no I don't do it for fact as well because I don't use fact very much it's it's just that this crap's really slow um okay we have to be slightly this is fast enough right if we comment out this that's fast uh okay let's just say uh list map is Prime and um that's not really what I want I really just want to go through the prime numbers check them but that still isn't that they're hard right like I'm not just an idiot right like this isn't like obvious I don't know sometime I me people are just way better at math than me and like it's like oh them oh well don't you just remember this identity it's like Jensen's inequality bro I'm like okay I mean I guess I wish I knew things like that and then I question like is it just big builtup pattern match or is it uh like a real thing to know umal I okay we don't really have to do this we can say um this map is prime n just enumerate M uh maybe filter Lambda X actually I can just say filter is prime range right that'll just give me the numbers that are prime and then I can try like r m in mm if uh P sub m = m c = 1 right stupid comprehension oh okay I think that's right yeah okay so that's the number I thought it was um so now we can actually plug these things into uh should work fine it's all mod okay cool okay so this implementation does work it's just a little uh slow q p and Q are just a and b it's a typo um yeah you're probably right about Frameworks of thought and then like you know you think about when you learn Frameworks of thought and I guess it's at like a really young age and then you realize that like the hacker skills are just a framework too when you just see things other people don't and I've met people just see things with this stuff that I don't um I don't know like I'm I'm not sure how much it can it can uh you can learn this but um if you appreciate this stuff please subscribe to me I'm never above Shilling you should never be above Shilling okay well this is combinatorics for idiots um but it is right so now let's just figure out how to make this code fast now this is the kind of thing where this is a correct implementation and if the compiler were intelligent it should be able to read this code and replace it with the closed form but as we know intelligent compilers do not exist all right so let's think through what this is um I think it's okay we have we have our three numbers here maybe a better way to think about this is to start with n factorial and just take out the ones that are incorrect so we have in factorial there's some why are they wrong why does something not match we need exactly a certain number of prime things to be in the correct place and that's the reduced form so it's like not a simple division we need a certain amount of maybe we can maybe maybe the the way to think about this is to uh oh they probably are data mining all the code probably the way to think about this is to say what's the inverse of this then we can subtract it from all the possibilities right so what's the probability that we have a partial Arrangement such that exactly K prime number discs are found in their correct positions if there are P primes less than n then P minus K primes must remain in the same positions yeah yeah yeah yeah I have that uh so let's see yeah we need we need P minus K and this is like a a choose kind of thing right so it's p minus k out of P we choose P minus K to be in the correct positions yeah yeah yeah so this this correct position and wrong positions thing is maybe a wrong way of thinking about this maybe the right way of thinking about this is exactly a certain number must be in the right position I mean and we can we can we can oh yeah I mean this is I didn't actually need to write that I think I just need to write that you can check if it's still correct yeah it's still correct okay so that that's all we have to think about we just have to think about exactly P minus k out of P things no I know the the whole Prime thing is just a troll um so let's let's just give P minus k a new name uh I don't know um P minus K discs in correct positions so so it's like P minus P choose P minus k or something yeah this P minus K fixed things but we don't know like you can choose which one out of those things you want to be fixed uh no but then the other ones are are wrong right I like this this this is how I know how to do things okay so let's just say Cal P minus k put that up there we're Computing these things C pause yeah so yeah see things are in the correct place and we can choose out of P to pick those C things but we have to pick exactly that many I always just worry that it's like beyond what I can do you know I don't know I don't know there may just like sometime when I'm when I'm thinking about this stuff I I think that like whatever combinatoric thing this is it took some guy like five years to discover and then how hopeless am I just trying to figure this out right like like how do I take this and turn it into a closed form okay so we place what what's throwing me off is like we place exactly we we we can pick C out of the K to place exactly in the right place but then how do we know we're putting the other ones in the wrong place I guess that doesn't matter because you'll always have enough out of the other ones is that true no has to be exactly has to be exactly that in the uh in the wrong place yeah I remember one time I tried this like RSA thing for days and uh no luck I posted on my Facebook and actually Sor solved it of iPhone jailbreak Fame I was very impressed okay n factorial or total let's just let's just play around with this so let's let's get the ones that are in the how many ways are there to pick C from P so that's like P choose c yeah binomial coefficients so we can say something like let's print uh NCR PC right so that's the way to pick four and also returned a stupid float of course this four I mean I guess that's it's obvious right because there's there's four primes and we're choosing three so you could just leave each one out right um so this thing does divide four just got to figure out how to get this number so we also need now okay so once we've chosen the ones that we want to remain fixed those ones are fixed now we're left with n minus C of which k yeah so we have to deal with the fact that those ones have to be in the wrong place so we have to exclude those which have is it K in the right place yeah we have to exclude ones which have K in the right place so how many of them are there well of the remaining ones um please subscribe of the remaining ones we have okay I didn't have to do that three that's not true in this case actually in this case three of the primes have to be in the wrong place three of the primes have to be in the correct place so then only one of them is wrong um all right so what if I just print NCR P2 C so those are the ones I'm leaving in the correct Place times factorial of the remaining so this is going to overestimate a uh factorial the remaining is n minus C so this this number is going to be bigger than a we have to exclude some yeah yeah so then we have to exclude how many this many um so maybe you can subtract to get that number all right so we want to know out of these how many have those ones how many have the P how many have the remaining in the correct place I don't know what the hypermetric G distribution is okay so that the problem with that is that's counting the ones that have things in the correct place which we want to remove let's try that no probably not going to get this by guessing um probably shouldn't try guessing Okay guessing guessing is a bad strategy we have to try thinking uh so choose the ones that we're putting in the correct Place those are done we don't even have to think about those anymore we have n minus C left C is p minus k K what is C in this case C is three I'm getting confused you know p is 4 C is one so we choose one prime to put oh yeah yeah because because four choose one is obviously four okay um we choose one to keep in the correct place now oh well so there have to then be three that can't be in the correct Place yeah so it's not exactly fact NC minus1 um say minus 3 and let's multiply this by 8 * 7 * 6 is that the number yeah that's the number we have to exclude right uh oh well that's the number we have to exclude [Music] yeah so you guys see where I got 8 * 7 * 6 from because there's there's one less possibility for each of those ones um actually maybe the whole answer no it's not right uh maybe the whole answer is just that right because we're choosing the ones to stay fixed then of the remaining ones we're getting it's close I don't know if that means anything but okay let's let's let's go back to a simpler uh so it's that thing I was trying before that kind of seems right it gives me that answer again okay well we know that's not right again because I'm forgetting something uh what AM my okay it well so if those choose okay do we have to like place the other ones first after we've chosen that that's just done okay there has to be you know what we could just look up a formula for partial derangement here we go here examine the number RK where [Music] exactly K items are in their original ordered positions but I mean yeah that's effectively what I what I wrote why is this x oh and the sub factorial okay yeah I mean that's that's exactly what I wrote this is exactly what I wrote here um and that would be the correct answer if we didn't have to exclude the ones where the other primes are in their correct position so this is the formula for partial derangement the problem is that we have some out of those yeah we need to sub we need to substract values that contain primes the whole primes thing is just a scam uh where exactly K items are in their original ordered positions yeah so that's right but it doesn't say anything about the other ones there is some clever way to subtract act here um exactly K items so we can say that out of the other ones maybe we can say up to yeah don't this is getting at good at least I'm happy that we're on the right track at least that kind of matched um kind of matched what we had so far but okay the problem is that out of those 1.4 million some of them have primes in the correct position so there's there's three things in here three given things cannot be in a certain position okay so any of three given things okay so I I then I I guess I don't understand why I was wrong when I wrote - 3 * 8 * 6 7 * 6 cuz that's not right like you can see vaguely why it would seem to be right how do I get three so three is just K which is actually the number that I'm being passed in um so nus minus K yeah uh well first first let's confirm that these two things are the same so I I think it's it's this if we want to say you see I I was trying to subtract one from each of those numbers to exclude like the position yeah okay so that's the same I'm not exactly sure why that's not right okay so when you look at when you look at the first first one it's like H the first one there's one spot it can't be in I don't understand why that's not right I'm going to be an idiot I'm just going to do it again and hope it's right this time yeah we're going to do that but it's still not right it's close let let's think of let's try to figure out what this is excluding that's actually okay oh any of three no but no they all can't every single one of them has a position that it can't be in the problem is if this one has already grabbed the bad position of one of these yeah see the problem so if I place the first one I have eight possible choices the problem is some of the eight possible choices are these positions and then that would actually give them all the possible positions do you see what I'm saying can I explain the problem you got to just rewatch the whole video I don't know uh uh yeah the problem is that once I've placed that okay I think we can actually write this let's just write it by hand okay so times 8 from is the next one's not times s it's not time 8 either it's time 7 / 8 no yeah but okay so how often do I pick there's probably an obvious mathematical construction for this um so it's 8 * 8 because there's eight possible positions if I put it in one of the positions let's talk about the next one right so you can say It's Time 7 but that's not really right because 1/8 of the time it's times 8 so we say a divided by 8 times seven of the times it's that oh maybe that that's right now we just got to do the last one so the last one is well okay it's a happy hacker keyboard God okay oh that solves it for that and and this explains why it's slightly under because of these ones that we're excluding if we can try to figure out just how many we're excluding we first engineer this by numbers we should probably be using a smaller example oh that's like a nice sounding number that's how many we've excluded right you know what let's just try to let's do this and then let's add back in the ones we've excluded right that's probably the easiest way to think about this so let's say that now let's look at the ones where we placed the eight in the seven hole so that actually means there's that seven hole eight [Music] choices for next where we placed the seven in the wow this is six hole this is going to collapse to something reasonable hopefully is this how people do math okay now we have to go back place the seven in the six hole okay now we also have to ask the question about where we place the eight and the six hole so that's probably 7 * 7 too big something like this is right though well actually if something like this is right we can make a statement we can say that would have to be some multiple of this and let's see if it is wait no that's not didn't it print a yeah this so is it true that this is some multiple of this and if so what multiple is that right is that exact be exact oh 356 perfect okay so we just need if we just take this and we multiply it by 356 that's correct let's check okay now we just have to figure out how to get 356 yeah cool cool that's correct okay how do we get 356 it's some crap like yeah well what's 8 * 7 * 6 we have to add 20 somehow oh guys I think we're getting close in before I sit here for another hour all right we got to get 20 how do we get 20 um so that's 336 is that right 336 and then there's another 20 somehow so those numbers are all way too big uh what's 20 + 7 + 6 - 1 + 7 + 6 - 1 seems right we love guessing math who's smoking crack Don't Smoke Crack [Music] kids I don't know about the expert ones yeah this is supposed to be medium I don't know all right cool all right now in instead of writing m in this stupid way let's write it correctly for say = 1 for I in range uh so what number is this how do I get to this eight so it's nus c-1 to n - c - K -1 - one that's probably actually minus two now it seems all right okay M * equal i m+ = i m - = 1 oh yeah that's fine because I have that minus one there all right perfect okay so it's probably wrong but we'll get to where it's wrong later don't need to print any of that these things are just stupid didn't mean anything definitely get rid of all this Ider tools crap doesn't even do anything that can be commented out B is not defined oh well we just know that b equals fact n did I write fact B well that done I fact basic programming cool all who thinks it works I don't all right it's all wrong okay well I didn't expect it to work we'll see we wow okay well that that's great they're all totally wrong okay so that's like just Library code above line not RW I wash my hands is m still hardcoded where's M no oh wait what okay well I meant to delete that crap great job you are good bro all right well that's maybe useful for something that's definitely why it didn't work at all I don't think CN is CN used anywhere CN is only used in broken stuff that's all broken this stuff doesn't make any sense okay well we had an obvious bug um CN is not used number of discs in correct positions get rid of that to perations and I think this is all still wrong because this isn't fast enough but uh okay I mean I don't exactly understand why this is true but no I I guess it makes sense maybe no it's just justifying okay let's try it again we're gonna get more right this time all right well we got some right yes this is basic programming yes and there is hardcoded but that should be hardcoded uh wrong answer wrong answer no okay it's still really wrong um I don't know okay maybe that 20 just isn't correct okay so correct times any [Music] placement let's be a little bit more careful about how we get M I think my m is m is the sketchiest part of this the 356 fact n minus C which we've already placed minus1 ided fact nus C minus K - one what okay so we have to get another 20 from somewhere the problem is that if we placed the first one if we place the first one uh which you had eight choices of placing oh I love chewing ice Bros it's a wonderful feeling [Music] um so we have like nine possibilities right we have to think through what happens if we place so there's one that we just can't place it in and and that's already covered basically how many combinations okay so this is all the combinations where none of the primes are the thing is the primes can be placed incorrect the primes themselves what this is excluding okay so we have three primes um what this is excluding is when the primes are basically they're all outside the set now we're saying that like we couldn't have placed no no it's not right I'm sure there's a more elegant way of doing this too you know what I know want elant why let's just see how many of these are correct this should be completely correct except for the fact that it's going to time oh okay if this is getting stuff wrong then the stuff we don't understand about the problem this isn't like some stupid thing like that right now yeah how is this getting okay if this is getting the wrong answer then the stuff we just don't understand right or like my is prime is wrong or something NCR doesn't matter if it's wrong I really doubt my factorials wrong wait what test K Zer worked before didn't it is my is prime wrong I know I wrote above line not wrong but like that really shouldn't break anything right I should actually be able to test all the way up till n is this wrong well first off I don't think the memorization really helps let's move mm up to here and and then p is just length mm print mm 357 this is not right how did that break all right that is a clever optimization stop being clever that's definitely correct I don't know let's just try is my is prime code wrong um I'm using the formula that's 25 okay it's not uh yeah like if this is getting answers wrong then there's just something I don't understand because this is just doing like how many of them timed out this should never return wrong answers um yeah it's giving me wrong answers it's timing out in a lot but it's also giving me wrong answer so we have a definition problem this is checking how many primes are in the correct position it's checking that it's exactly that and B okay I mean is this is this p and Q stuff uh exactly K prime number discs are found away from their natural positions discs numbered one through n oh that could be what's wrong the discs are number 1 through 10 not zero yeah do that too cuz yeah n is the prime stupid math people with their off by ones you can figure out what that is later but let's say no still wrong there are n total permutations that's still correct Zero's never Prime so that's not even a question there that would change the the length slightly um no there's a ton that are actually wrong oh runtime error well that's a different okay is this still some off by one crap oh okay uh math people that I have to check the index of the array right it's amazing that it was right at all the first time let's see is this right now ah okay we're still getting some wrong ones up there but this is definitely uh uh maybe less wrong okay so I don't know I mean the other ones could all be timeouts at least we're getting the simple test cases correct now um now let's go back to our see it's always important to get the not execute within okay these ones okay we're still getting runtime errors um that's weird I wish it could you know tell me what the runtime error was but I guess if it told me that it'd be cheating uh when are there run when could there possibly be runtime errors can these like be negative or some crap or you know what this no that should be aish ient modular power should be efficient this should be efficient I mean I don't know runtime error can mean a lot of things okay let's let's see if we're getting so we're getting test cases uh 0 through five correct so now let's see if we get it correct with the close form by the way this here is the derangement formula like don't think I'm not using the formula I derived it it was simple okay wrong uh only because I'm printing M don't print out so p might have been wrong in those cases so that was actually something that the off by one ER caused okay so a ton of these are wrong the close form does not match the other form um would the off by one errors cause this no they wouldn't they could have caused P to be wrong but that's probably not the issue look we're getting test at 8 correct well at least we're not timing out are those runtime errors oh no we're timing out okay some of them time out problem for later okay uh 356 well that's correct so that's 336 we're back to ask asking the questions about whether I got 20 from a really sketchy Place well so what if we instead start out with just the formula and we want to figure out how to subtract the bad one the bad ones have any set of three primes in their any set of three things in their correct place so there's three it could be one two or three that are in well it's it's k out of those n minus C there can be K things that are in the correct place that we don't want them to be so why don't you Google where did I get the derangement formula it's right here that is exactly what I wrote create input from standard and print input to stand stand out very good we're doing that oh you found my error oh oh the oh the the the the the N is different from oh sub factorial oh maybe you're right what's a sub factorial wow that's a scam all right all right all right we were wrong sub factorial No Object appears in its natural place yeah I guess I should have paid more attention when they put the exclamation point on the wrong side all right D mod thank you please subscribe even though I don't know what a sub factorial is all right you were right about the E shit too yep yep yep the hands to wash you know what they going come back dripping all right yeah I mean this here is like what I'm deriving I think the sub factorial shit right because it's not sub factorials seem to be a question of exactly K items are in their original ordered positions right so this isn't to be fair what happened is I misunderstood the uh partial derangement so it still isn't exactly this right in which exactly K items are in their original ordered positions um I think what I'm trying to compute here with m is a sub factorial all right so maybe we can just take the equation here and figure it out um satisfies that yeah yeah and I think this is right here satisfies the recurrence relation n * the sub factorial of you want to just copy that formula m is a sub factorial see I derived it all right all right all right imagination you're you're right it's still not the right answer though I just want to make that make that clear um if Nal equal 1 return one return n times should we try to like learn instead of just copying let's try to learn yeah that's why that like stupid minus one got in there but this is this is the right thing subf n minus one plus -1 * * n why is that bigger definitely shouldn't be bigger how are sub factorials bigger than factorials put it up there by fact did I I just minus isn't it+ -1 to the n n times the sub factorial are sub factorials bigger than factorials does that make sense well maybe for and for n equals oh it's zero wait no that can't be right though that's probably right is it smaller B smaller oh good it's smaller now okay so now we want to say something like fact well we know what M has to be so let's just say m equals Suba Maybe if I just replace these facts with sub facts it'll work you love how I do math guys come on 356 337 maybe it just a fact 123 no good no good 337 was pretty close though maybe this one's a fact all right all right I'll stop being stupid now okay um in reality we want to like just stop Suba early so this um so we're going to say m * equals I not right okay okay I don't know who kabib and porier are uh let's all right let's let's think for a little bit um so we need Let's test our sub factorial function 44 huh that looks good okay wait so we put in put in five and six and we got 44 and 265 so that's 1 2 three four five okay that's right um so those can be placed anywhere there's last ones but out of those three they can't be placed anywhere oh what is just that the problem is I had that janky minus one in there where maybe I didn't need that I don't know if sub facts work like factorials like that no they don't seem to you see the problem right okay so now maybe we can read the ones in where it doesn't matter how they're placed the problem is there's how many that we don't care where they're placed n minus P that we just don't care where they're placed the problem is this is excluding all the ones where those are placed correctly so if there's n minus P that we just don't care where they're placed then yeah this is excluding all the ones where any of those are placed correctly oh this is getting hard where any of those are placed in their correct place no we're better off going with what we had before we want it to like not become Suba at a point so maybe we should just write a custom call it lame fact if n greater than k is that right no not right think what we actually want see is that not CK okay so for 9 8 close see what I'm saying though is this going to require us to understand what these things are that would suck I hate when you have to understand and you can't just proof Force Pro Force is great proof force is the solution to all problems it's too big too big of a number okay lame fact didn't work so those will those are okay with it being placed anywhere those so this is going to be smaller cuz those are just the derangements all right we can go back to trying to add them back in p and Q are just a and b uh I'm go back to trying to add them back in so this is wrongfully excluding anything where M should be 356 so we have to figure out how to get 356 out of this let's let's just look at the definition all right let's go back to where we were you threw me off with all this we we we were close before we really were the subf fact n that so that's the hm all right it's a common comor trick to like double count some and then subtract those out so okay [Music] all com even bad drink te that's all the ones they wrong nine 356 these divid nicely I don't think these ones do you sub factorials just don't divide nicely I have to do some other subtraction stuff right okay none of them plays correctly any shot it's that it's not that okay so that's any possible placement of those it's like the problem is in this 876 thing if we understand why we had to subtract one maybe then we'd understand why are the sub factorials this number of permutation of n objects where No Object appears in its natural place those ones after that we don't care could it be this okay like so this is this is this is under Counting I got rid of what the right number is supposed to be for why is this true it's not obvious n minus one hate generating functions a 356 for okay so start here this under counts because there's n minus C minus K that can actually be placed anywhere that here are not being allowed to be placed anywhere so if we add back in all of those possibilities right how that's not easy though what I'm not reading your paast bin guys we're going to solve this I'm okay if it learn if it teaches things like we're so close Okay I we I guess like M should be something that we can calculate the problem is we're just we're just excluding some of the possibilities an M I had this I had this worked out before okay we were excluding the possibilities this really yeah that's right I don't know why that minus one is there that's the thing that's throwing me off makes you think that this just might not be right at all um Suba and C but it excludes all the possibilities where I don't like for me to understand this I'd have to understand how sub factorials work and I I don't yet there's this other relation for them that maybe is maybe is is just more correct right so if we want to figure out the sub factorial of n we can just m we can just say and like we can even probably get rid of that because that's probably just going to fall out let's just okay let's let's just write it let's just write the whole thing out all right so it's it's 9 - 1 stupid we can't we can't get I mean that's not that's not obvious how to get that like the only real way to get that is with with recursion stupid plus like it factorizes right span thank you for subscribing yo I went to the bar in New York uh it's a that the hotel Tesla died at is now a bar it's pretty nice um let's see okay what if we start with with that then we want to figure out how to how to add to that right so let's just say mm mm subzero equals uh fact n subk so what if we say that that's the previous sub factorial right now we say mm sub one should that one we can just do m m equals 7 * [Music] mm I think we can just make this m just pretend that's that's that plus one 8 * m - one 9 * m + 1 or let's see seven so one minus one so it actually be the other way around I the Right am 440 no it's not right 287 that's not right 385 that's not right this is the definition of sub factorial right I have the exact formula for sub factorial of zero gives one yeah but I don't care about the E crap right like we're trying to get an exact answer here um trying to get the number 356 so we can say okay M * equal 7 m * = 8 m + = 6 m + = 7 m + = 8 m - = 1 okay it's stupid but it does give the right answer 356 okay 6 + 1 7 no this isn't really what I want so this can be 6 * m i mean I want to like shoehorn the sub factorial formula into this maybe there really isn't a way let's see yeah I mean with the minus ones there just may not be a way uh I was trying to do this with lame fact but 7us one oneus one no that would be if we continued the sub factorial formula this is six right yeah so that would be like if see see I want to combine basically a factorial and a and a sub factorial don't talk about comma here if I hear any talk about comma bam oh just how do I get 356 in a repeatable and reliable way you don't need the shit these shit's useless if you figure out how to use the eshit then you know what you go solve the problem because I don't think we need the eshit okay we got to just use counting arguments like proper counting arguments I'm even bad because the okay exact partial derangement formula the number of derangements is just the sub factorial yeah yeah yeah yeah inclusion Exclusion Principle this is what it is oh I remember this I remember this okay yeah yeah so it's the inclusion Exclusion Principle if we're trying to get a union B yeah inclusion exclusion inclusion exclusion it it's this satisfies the recurrence relations see how long did it take bruli to solve this that's the real question so 356 is some form of inclusion exclusion okay so let's say we start out with 9 time 8 * 7 which is the remaining but then we have to exclude the ones where here start out with all of those but then we have to include the ones where the first one was placed in one of the other two holes no no no no no no I don't know f can we start with any of them but then we have to exclude the ones where the first one was placed wrongly so that's just 8 * 8 * 7 which is not right either like something like that though I think no it's not that um okay let let's really let's really just try to think this through the beginning the problem there is just we aren't Counting coun Ing we aren't counting ones where this one oh oh oh is that right yeah it's 356 okay no well it makes sense to add six right for imagination I appreciate you with the subfactorial stuff before but you're on the nice you're you're on the nice let's just let's just say you're on the I I can't clusion exclusion right like we're getting somewhere with this shit add parentheses well it's not a parenthesis problem it is something like this that gives that thing though 7 * 1 it does yeah okay it is obviously that right like we don't need to actually add those parentheses um okay so what is this generically we have we want to do 9 to 7 but without so what what if this number were longer right like let's see if we can figure out the generic pattern right so let's say it's 9 * 8 * 7 * 7 right then to follow the pattern would be okay this isn't obvious at all never mind never mind this is stupid we have to truly understand how sub factorials work until we do we'll never solve this problem [Music] okay let's think it through in a small case let's think it through small case time small case you're getting imagination you're up the ice drinking tea and peeing is the absolute joys of a Saturday morning is now becoming a Saturday afternoon drink some more tea calm down we going to solve this problem ah yeah you like my futuristic Furniture bro okay you know what I I really don't like how big this text is I can't see my code let's start with that um I'm I'm just stupidly trying numbers let's not stupidly try numbers let's be intelligent I really just want to compute M because there is an M there has to well maybe there's not an M may maybe just the fact that this works is is just a scam we've already placed those we're left with a question of nck placed anywhere n minus C to K not placed in a certain spot and minus C total what if I just say and minus equals c that's already taken care of just need to multiply by a Suba n would be all n not placed in a certain spot fact n would be with them placed anywhere so if we say a * equals fact n minus K times the magical 356 we get the right answer now what we should do is we should use machine learning to take in there's some function of n ink which outputs 356 right we really boil this problem down now look we're trying to be constructive okay we don't know that that even always divides so this might not even be true not placed in a certain spot right so if we have fact in we want to let's look at the inclusion Exclusion Principle for I'm trying to get the union so that's not right because fact 's already overcounted them see thing is there's great ways to get at this with factorials and it's like this like you almost feel like you want the answer to be this you think that should be 356 right like that's what you think the answer should be but it isn't that oh okay um Suba n under counts because there's a that can be placed anywhere so deliberately excluding ones with K's placed in certain spots okay so let's go through okay let's go through let's go through Suba and excludes let's say for one of the ks how many spots could have it been placed in only one right and then out of the rest of them how many of them could have been placed so let's place that specifically and then say of all the other ones after we've placed that one specifically in its one spot which was excluded this is close it's not close okay the problem okay what this is missing is that see if that's like a multiple it's not so we're gonna have to add is that right it might be that no it can't be that because I added all the subs no it's it's not even enough if you add but it that does seem like that's on the right track that's still too small that's all the derangements of all the other ones given that the first one was placed in the one spot it's not allowed to be placed in yeah we're way past any of the Prime shit but we're just saying we have K that are not placed in a certain spot and all the other ones we don't care about right oh it's actually all the other ones we don't care about so it's n minus k um the way to solve the problem is go backwards well thanks bro now this is going to work out to what we want but it's close to this okay we have to add back in for for let's let's pick one of them let's pick one of the K and place it in its disallowed spot right then of all the others we have subf n minus one but that could actually be true for any of the C okay [Music] so we're going to say this could actually be true for any of the N minus k something like we're getting closer we're getting closer all right there's more because there could be two of them placed placed right so too much the two is already included in the above okay 93 um [Music] Suba dkmo is that actually right no see okay I don't know we're close with this stuff right so any of the N minus K any of the six can be placed in their correct spot and then all other derangements are allowed but the fact that their derangement promises you that none of the others are placed um so let's see how many possibilities are there that two are placed in the correct spot right it's it's not actually it might so that two how many how many this seems intuitive but it's not this that number is huge definitely not that oh well choose two so this shouldn't actually be this should be a choose um n n minus K choose one M minus K choose 2 K choose three so Factor minus three I think this sequence might converge to the right thing right and then like 626 just has one possibility is this right sweet right it's this I don't know if there's a way to collapse that down but okay does everybody understand why it's this uh I think for completeness we can even write choose zero here chose zero is always one assuming my NCR function is correct yeah all right it's not Brute Force I mean let's so let's just just write this as for I in range uh 0 to n minus K plus equals minus I pretty sure this is right yeah what huh can we just have it right is that not the right number off by four what oh do we not have it right before what changed what broke it that's right what do I do for a range oh I guess I didn't include the last one um cuz first off a a equals Zer this is a sum plus that minus minus I this isn't brw Forest guys is that it's like very reasoned whyus k + 1 so- k + one will go to six okay now we have the right answer now we can comment this out this may be too slow we may have to figure out an even more closed form okay I don't know why we're getting one and two wrong and getting all these other ones correct it's probably some bug or typo or something all right we're getting close we're getting close what do I think of the colon it's okay we're getting close we got most of them correct we have runtime errors how do we have a runtime error um so we can also make this I don't know if any of these are timing out some of them are we can make this a ton faster for I don't know how fast my NCR is but okay so most of our remaining bugs are some runtime error we had that with the Ider tools one too let's make sure all that's commented out yeah where could there even be a runtime error no reason to memorize that we memorize this Prime the denominator be zero here yeah that's probably what it is probably have to deal with the degenerate cases of uh NCR so I don't know what the uh degenerate case Solutions are here but like yeah that's going to end up being a divided by zero it's going to end up being a divided by zero if well I guess if r equals z can r equal Zer in any of our things um if r z turn one so we're taking I guess this there one way to choose zero is that right I going to fix the rtime error I fix some of them where else do we do division I mean that's the only runtime error I can think exists by the way there are really cool ways to leak information out of these problems using that right like if it tells you there's a runtime error you can like leak a bit right uh halt versus runtime error thanks for the bit leak bro uh okay wrong answer well that's a different problem so maybe the answer here is actually zero maybe this zero is zero ways to choose zero there's not zero ways to choose zero and it's offended for me even suggesting that oh I guess no that's not even a problem because it's not going to reduce to it's not even being divided by that's just wrong okay runtime errors are still happening the runtime error is probably happening somewhere else Auto mod my favorite IG thought yeah I'll allow that of course thoughts allowed asking me questions about my personal life or Comm AI is not um we're getting close look at all them look at all them check marks you know I wish I had a check mark on my Instagram um okay where could there be bugs where could there be runtime errors let's just see if it makes it to here or maybe we can test it on a few examples test against custom input I don't know here we go oh maximum recursion depth oh that's a good point my Suba function is shit if Nal equal 1 returns zero that was in the definition uh still WR um well maybe actually we try all right we got some number out now it's not test against custom input let's submit it those ones are wrong but I don't know about those those ones might be out of time or something come on one and two oh we got one okay good now all these ones are finishing and I think I hope those are all timeouts um in which case runtime error some of them are timeouts but this is a this is a more clever runtime error I think maybe it's overflowing some shit I don't know let's try big numbers 10 million and a th000 let's try you know it's overflowing just mod every number runtime error I don't know why that's called runtime error could it just be is Prime oh yeah we can add my uh speed hack back to is prime otherwise that's N squared yeah my is prime function right now is n SAR let's just say in square < TK n + one math. Square we also don't actually have to build the list here we can just say p equals ma uh Su map is prime range n+ one is this more of them failing it's possible also this runtime errors on the output like those pals are overflowing overflowing yeah I mean I guess the factor can get really large right we're doing B we're doing n factorial which this factorial is a huge number yeah that's a lot of yeah that's a lot of digits okay well that's why it doesn't work oh okay well good news is all of this stuff is junk and any shared we could do the no but it's not actually it's not the primality that's causing the problem my primality is now nun n which is fine it's this well okay so we know p is about Ln of N I don't know I'm pretty happy I think we solved the problem I think um we just wait for computers to get faster and then we can solve the other ones [Music] no you know what that actually is the runtime error is recursion depth being exceeded in the factorial function um I me we can fix this uh r equal 1 for I in range x r times equals I there's no reason this has to be implemented uh now we're going to get timeouts hopefully instead we're still getting runtime errors I don't know but we can check if that's actually already happening by here for we'll see if those are runtime hours in which case we're going to have to really think about what this is and where these things are big just wrong answer okay it's not there let's see if we're getting a runtime error by here all right we this is kind of cheating oh Suba could have too much recursion yeah okay we'll write that on recursive too all right who wants to do e shit is it just e e is the usual runtime error okay so it is caused by recursion in the Suba function I don't know um how much Subs do we need can I just pre-compute all the subs because there won't be recursion if I pre-compute them all oh yeah yeah this is actually a stupid way to do this um for J in range uh all the way up to n subract n preach that won't have recursion limits right or I don't know might I shouldn't though cuz I'm pre-caching them all all right who sees what I did who sees what I did okay woo we got a green check over there love my green check mark they're not blue check marks but they are green okay these are probably all timing out I think they just need to buy a faster computer that's my thoughts on that no no no guys no no no we can't do that we have to win we have to win but we're making so much progress we're getting almost all of them right you know someday I dream that the computer can just deal with this shit for me okay the problem is that the factorial of 10 million is just too large of a number the problem isn't even the for loop I mean how can I optimize the for Loop we can talk about that but but I think we're actually just dying here right there's no way we're getting the factorial of I mean maybe it's like a 5 megabyte number that might be okay I don't know well so here's an interesting realization I believe that we don't ever actually have to compute that I think we can do it inside of here say just T = 1 right it's just should a ring right so uh 4 I in range n one comma n ttimes equals should be the same right nope not the same why not oh cuz it's inverse that still should be the same right [Music] wrong answer oh cuz I changed in oops um this is why you should stick to the single static assignment forms when you are writing program because the single static assignment form doesn't do this wrong that's the same wrong answer I had before maybe one's not the right number to start with uh my point is okay you know what no I think the factorial can be done in the modulus yeah that should be okay if I do the factorial mod n right so say like b = 1 for I in range n b * = i h sorry old n and then if we put B there this is okay okay why not if I make this fact old it's okay right yeah huh why is that am I is that not the factorial function oh all done plus one did I just forget a plus one in the other one to well either way it doesn't matter okay this should be fast relatively right I mean yeah that's that's all it um now we have to figure out how to make the other thing fast the subax I guess we're doing it all in the ring so it's fine um we just need to preach the Suba yeah y yeah you guys you guys see what we do right BTM thank you for subscribing thank you for subscribing you are you're uh yeah we just do does it terminate through timeout if I get rid of that probably still does if I just take this n yeah everything's just mod in right so it's right isn't it I don't know about pluses pluses might break mods that's a later problem though pluses don't break mods I don't know what the time limits are is it possible now that I'm just no well so this N - k + 1 K should be relatively small this should be anog n that's not really fair now is it I mean k should be small has to be the largest possible value of K is is is yeah n it's kind of big let's copy and paste this and put it somewhere safe Monica Subs scream thank you for subscribing I appreciate you uh Sam the program what is this you guys are talking about I don't know I mean the NCR thing I guess also can be this first just make sure we didn't make any mistakes God oops CU I didn't Define until there how did any of them run maybe this isn't right okay so let's look at the chooses and see if they're going to be big p2c that's probably pretty large um yeah I we might have to just rethink how we're doing this core thing that just might be too slow let's think about it okay we've narrowed it down to the sub problem Oh I did triple bite I scored in the top 2% now they keep hitting me up for interviews you can work at Great companies like Cruise automation oh wow Cruise autom wow um what is this this should be okay actually if it gets to here within the time limits we can fix it because this here is actually yeah we can figure out how to more quickly do all the ncrs because they're all in order this should be like a event right no these ones are still timing out but less of them are timing and now it might be the same ones starting with 26 is timing out is that the same ones the time out if I submit it no there's more timing out okay so it is just this being slow uh that stuff's definitely not slow this here yeah it's only because it's doing that reduce um so what is the formula for NCR this you know what we're just going to replace factorial with a uh and this should scale right it's only going up to 10 million unless they have some small stuff we should be okay two to n uh this is just slow by Design This is after we've R in right that's before we R in that should be real fast right one more okay so now we can leave that NCR but this NCR we have to make fast um fact n minus K ided by yeah okay itimes fat and minus Kus I there's a lot of ways we can make that even faster I'm aware we'll get to that in a minute okay well because I didn't use that kind of division see if this is more correct was finished fast are they wrong you might have missed the same exact ones oh no we got okay good yeah okay it's all just time limits still um oh mod app it's not right oh it's not right why is it not right because that divided by is not a divided by anymore then it's not that the factorials are wrong it's that we can't divide like that is there another NCR formula that doesn't divide dividing is really just a way of subtracting oh you got four test cases right nice job you're getting there one day you'll be a elite hacker uh use my sand trick for inverting I think I don't know if this keeps any of the performance guarantees but might be able to cat those in linear [Music] time that's a lot of correct looking ones all right good we're getting less wrong now now we're getting only the ones wrong that were wrong uh before now we're getting the only the ones wrong that uh that exited early oh man this is a lovely Saturday morning guys I'm happy to have all of you here with me and we're going to solve this problem is we believe in ourselves you know I don't know man all the Millennials who are raised on that kind of we believe in our sh self shit code did not execute in the time limits I know I know we're working on it so I think it's just my is pre-caching all the factorials too slow let's see if that doesn't execute in the time limits I don't know what their time limits are this I feel is a fair test because this thing would probably run on my computer okay it is now ENT it might be my Suba preacher that's too slow for some reason shouldn't be though yeah these are not executing within the time limits oh is it actually happening before that maybe is my Prime thingy too slow oh that would be great if that were the case that we can make fast I think yeah so that's nunk n that's not that's not fast enough yeah that's the problem it's acquiring 10 billion Ops water we're switching off T we too hyped on the tea bro got latte this morning too you know yeah yeah yeah the prime shit's just too low okay too slow um fast way to count primes below n oh wow wow these look complicated the seeve of arath is okay we'll do the seeve of arath that's not it's still not in maybe there's just not an end time algorithm for that Al so first off the memorization is all crap cuz we're only ever calling any of these once don't need this all right maybe it really is just the see ofne let's go uh okay PP equals true times uh n + 1 PP Sub 0 = false PP sub 1 = false for p equal sum PP get rid of that uh this was not an easy problem guys this has a lot of parts to it I admit that I was a little stupid for that for that NK thing I mean like I got it as soon as I simplified it I was just uh I don't know I I left in the minus C it was confusing me I shouldn't have done that uh so we have to go from this to this forn in range this can start with zero + one I mean I don't know like how is this fast oh I guess well we Skip by I and we say PP sub no no this isn't right um I * 2 PP no we don't want n here we want J PP subj equals false I think that's right do I still have an exit in there I think I still have an exit in there yeah okay so you guys see I just a see rathne uh maybe it runs time did I get any more right so if just the Civ itself is too slow I don't really know what to do we have to think about just how to do it faster no I don't think the subax thing seems fast think my SI is fast let's see let's see if that's timing out okay well it's timing out on a few of them but not that many I mean we're going to have to get them all right so if we can't do this guys okay okay I got an idea I got an idea Bros I got an idea who's ready for it who knows what it is who knows what the idea is who knows who knows who knows who knows does anyone know imagination what's your idea come on you guys can figure this idea out oh Ley you know well what's the idea not smoking crack we're not doing a tree and we're not turning off the stream we're not coding on Vim we're not doing gcds I'm not allowed to smoke weed in my apartment but that does sound nice no Aderall no no no oh Uber eat sounds delicious no second latte oh Ley you're very close you're very close Ley we're going to rewrite it and see there we go change theme we're changing the theme oh this is going to be hard shit's unusable all right because it's not like I can't even make this any faster it's not my thing is now ofen so that's not the problem o C++ 14 that sounds pleasant oh no we have to figure out how to read in int all right so let's go int NK CNN cnk is that right who knows c um C out 10 oh no we're gonna have to figure out how to do that I'm gonna have to figure out how to do that in uh in say which I don't know how to do but I I just I don't think there's a way to make this fast enough in Python okay perfect uh bu P up one for I to I less than I just do square root of n + one cast that to an integer P sub I in i = 2 for in j = i * 2 J plus J less than n j++ PP subj is true for okay I'll put a zero shouldn't be zero yeah I know all the languages have different time limits I know they try to compensate but like I I I don't know I don't think there really is a faster way to write that right and that's not finishing in time I don't know why it's giving me zero okay now it's G me one and I'll just trite the same algorithm it's even harder to write write this in this tiny little box six that isn't right I guess that'll make it right four four is the right answer okay all right let's run that and see if we're getting out of time erors I'm terrible at Minecraft guys I can't m a craft at all oh this is a new segmentation def fault what am I supposed to do about that big stack you don't like the size of my stack is that right compilation error is that the syntax is that not the syntax can it not tell me what my compilation error is Define size of array oh here we go array must be initialized with a bracket enclosed initializer that's what I had originally initializer fails to determine size of pp okay shows you how much C+ plus I know okay now we're getting wrong answer and we have one timeout but it's only one timeout so this seems okay this is an improvement how big is that number it's in an in shouldn't have to deal with too much overflows okay um all right I guess we want to pre-cache all the facts and their modular inverses there really isn't a faster way to do this guys if you think you have one I'll be impressed stuff matters really for like the small numbers uh two is going to add one so that's just fine don't need that that's computed right okay now we just have to figure out how to take inverses um um modular inverse C++ not going to work perfect thanks for the pasta a mod M okay so now we can just do all the inverse facts Ina sub I equals okay this stuff there might all be ways to do faster just the prime thing I don't really think there's a way to do faster uh mod inverse fact comma n okay seems pretty good right PE see the problem honestly I don't know if we have this much RAM stuff might not work [Music] [Music] for for [Music] uh yeah AI Winter's coming winter is coming hope everyone's got their coats hopefully they have 64-bit computers over here n was not declared in this scope what I don't even know in NCR okay well it's a number at least what do we do wrong four four subus oh okay well it's almost done right number uh for should be mod in why are those numbers so big for yeah I mean this is why people don't code in these stupid languages in fact subr in fact sub these numbers actually seem a lot more reasonable than those ones oh why is M minus K different where K come from oh I didn't subtract from n yeah that might have been all issue well the answer is not right but I don't know what else I broke 060 okay looks like the problem is only for uh I'm passing I equals z and the answer should be one they have some thing for that z turn one okay all those numbers match that last one doesn't how did I add up a bunch of small numbers and get that I guess because i'm multiplying it by Suba I'm not multiplying it by Suba there that gives me the wrong answer I broke the python I broke the python oh it's that's not the same as that the python is fixed didn't make the same stupid mistake there I haven't been talking too much hopefully you guys can follow along with this it's not too bad it's just porting just rewriting this in okay Suba doesn't match Subs here are wrong so in fact H seems like it shouldn't be why is that two four three is four it's not right n mod one that's right subf IUS one which three is not four okay so for 2 it's going to be equal to 2 * 0 + 1 so that should be one then for three it's going to be equal to 3 * 1 - 1 which should be two oh I make mistakes like that all the time okay now it's ging me the right answer okay well a lot of wrong ones this probably has to do with yeah so this is probably some kind of uh grounding issue somewhere let's just see where we forgot our mods wa we didn't even try why why are there no mods here mod versus already mod so we're good oh okay we still have some that are too slow we got a few more C++ for okay so I'm pretty sure everything's all B right I I don't know what's not I washed my hands Bros okay uh that that if the preachings are right already too slow let's just return here and see if these time out the mod inverse might be too slow yeah okay we're getting we're getting timed out here maybe it's the mod inverse because if if that stuff's too slow I just don't really know what to do the mod inverse I think we can if we're clever we can do better okay we're getting timed out on two but the mod inverse is pretty slow uh well so let's think about this for a second H here's here's here's an idea I don't know if it's going to work oh wait n is bigger than no and is too big uh pragma OMP parallel 4 yeah I wonder if that will work we really need the m is that if all we're doing with these is ncrs the ncrs it's still that's still probably the fastest way to do it like maybe we don't need the ncrs so also like we could mod inverse the numbers and not do it like this CU what is what is a modular inverse yeah yeah Sam Alman trustworthy guy they just took a billion dollars from Asia they call their organization open Ai and they post you know basically news tier gpt2 is like news tier flame bait like oh it's a moral ethical we're not going to release and you know oh my God and then what they did to that poor Connor kid you know Connor Connor Lethy he he reproduces it well he didn't really reproduce it but um oh well I learned that we have to set moral red yeah you know how we do this with an actual open conversation there was so many better ways they could have gone about that so don't listen to Sam Alman real shit well so see deep mind you have to respect Deep Mind Deep Mind never lied about uh what they were and it's not to say that open AI didn't do good work it's just I I mean it's it's right I think the people who should be punished harshly are the people who try to use open rhetoric and then are not open people who don't use open like like it's just you know it's a general hatred of hypocrites see there's two types of people in the world there's assholes and there's Hypocrites and uh assholes I can tolerate Hypocrites not so much I definitely think of myself as an asshole not a hypocrite I may look up arace I'm going to make this faster now like I I don't this is all ready it's all of n unless the mod inverse things not mod inverse things sort of not um but no I mean also these people like like they think I don't know there's going to be another AI winter I think a lot of people are are saying this deep learning solved a set of problems they're very useful to certain industries but that's been true for every other AI winter before this maybe we solve chess using massive search and then Google starts using that's just not even the same same search techniques I don't know I don't know what I'm saying just trying to make this faster how do we make it faster don't make it recursive there should be nothing faster than that I'm focused on this is there a faster way no I mean I'd still have to invert all the numbers up to n if I wanted to I could create the factorial in the modular space right hard code 10 million factorials I I really don't think that's the right idea um mod inverse is doing ukan algorithm like this is kind of slow this stuff shouldn't be slow at all I mean okay it's it's all the way to 10 minus K but still like this is a bunch of multiplies right like you can't even argue that that's yeah this is O of one solution this is the only thing here that isn't of one uh complexity of modular inverse o of M what's m the mod oh who likes this yeah yeah this is the trick we want right well it's faster probably this is the same trick I used in Python wrong answer why is it the wrong answer this is like the Montgomery algorithm there's ways to make that even faster too uh I don't okay why is this wrong recursive but n is definitely Prime that's right I I don't I don't know so like some things I can't invert or something these should be one for all them right cuz n's Prime it's not so there's a bug it's not even one for all of them what kind of power function is this oh I guess that's maybe I need to change these to LLS yeah that's probably not working oh does not name a type oh I'm G make it name a type I used to have like some copy paste shit that I would put at the front of uh all my competition programming it had like LL on stuff I wasn't expecting this to become like a hardcore competition programming see how we're doing think we're going to miss like a few of them still we're going to get more maybe not okay we're still slow time out let's see if it's timing out by here even log M wait what okay yeah it's it's still timing out doing the inverse all right well at least now we have simpler code um now there's faster ways to do this there's not that many ones in this is there that's a lot of ones great no okay maybe I don't need the inverses come on this is like this should pass how do I get more time this isn't really fair this is like okay infa R in fact and minus r is there any way like these are small or something no so any to do without the Divide great there was some other way how how is how is this one doing NCR there's another way to do it I mean they divide but they only divide by one thing I mean I guess you could rely on the fact there that K is pretty small what guys my math is all right I I don't get it I I don't know how do I make it faster maybe n minus 2 doesn't have a lot of have a lot of ones in it there a lot of ones in it modular power this just might be faster so this is like normal Montgomery I've written this algorithm a bunch of times in like microcontrollers what kind of a useless comment is that like I hate people who write comments initialize result well no shit like what do you think in res equals 1 does oh oh we passed test case 29 now we're moving up in the world slightly faster there really there's not a faster algorthm for this stuff I mean we can make that an INT that doesn't need to be we can make that an inch too but I don't think it matters sign didn't there someone to do this without choose has anyone ever solved this problem with haer this may not be solvable so long to convert from long to int I mean okay we can make them all Longs those can stay I mean this is this is now well beyond what anyone should be thinking about okay is it failing all before is it failing all still in my pre-c phase yeah I mean these are all failing here okay maybe I don't actually need them all this is unfair though is it failing before the primes even only 34 I don't think so and it would be nice if I could pre-cache the values once oh let me see is faster oh shit no no no no no no no please come back please come back oh few uh if that deleted my code I would have cried I think C is I don't know I don't actually use C++ 14 let's start with just C++ maybe that's faster go NOP same ones who thinks C is faster well okay so I don't have to do these Alex I can pred declare them um it's 10 million yeah we let the colonel do that crap I don't know if this stuff's faster same bad ones but actually I don't think I think if I just change this type defa to a Define LL unsigned long um um no I can't imagine there's no way C is actually faster than C++ yeah I already used the modulus and the stuff everything's in the modulus frame I mean and it's failing like like if you need to invert all the factorials if you even need all the factorials I don't know maybe this is just some really clever clo form for this but I just don't like I don't know um vision is very high okay in other words hacker rank is telling me they want me to think not just spaming anymore well let's try this maybe we're wasting all our time on P and we can figure out some faster algorithm for that we probably can make that marginally faster huh only 34 okay so the IM isn't that bad it's just the combination of both that's slow um anyone have any ideas about faster ways to do the prime thing oh no no no no no if PP subj or sub I equals equals 1 one right because if it's already zero that means it's already just a multiple of something and then I don't have to do the inner loop I think that's right yeah let's try that no you see why I think that's true we go back to C+ Plus+ 14 it'll let me submit again because it didn't make me do this until no okay so if PP sub I equals 1 if it's not already ruled out by the Civ then we have to go rule it out right cuz we only actually have to do this for numbers that are prime read chat for 1 minute okay what do you want me to do you calculate square root every second inner iteration I don't think so do I I don't think it's that stupid compiler will we we'll do that better imagination What are you saying something if PP equals big where oh oh we got some more okay we only have a few failing now yeah I reading the wrong Parts what no okay we made the prime faster but the power thing is still slow right like they're both slow don't say I'm reading the wrong Parts if PP equals hard great you're funny dork mod thank you for gifting the sub you are bro [Music] um need all the INF y if Y and one I don't think C is going to be faster stop with the paste bin crap well I can't believe 600 people are watching this we're going to get it um okay so is the only problem left the in fact thing seems like they've started to throttle me because I'm using all their CPUs I'm racking up their AWS bill okay none of them time out anymore so the only thing I think we have to make faster is in fact we have to figure out how to not use in fact um a french guy solved it with python well you know I'm American we we we solve things with with F-150s and uh Big Max and yeah American yeah America we love love America all right um compute in fact this is what's slow it's slow because there's an inner loop here well the Y doesn't change we can precompute that for a y actually we can pre-compute that exactly for the Y don't need that but that's not even in the loop so it's not going to be faster yeah we don't have the X's so those we actually have to compute There is almost the fastest way to write that so we actually only have to compute it for the primes and we can make all the other ones out of primes but that seems like a lot of complexity Y and one I'm not reading subtract Suba equals yeah no that's not the problem subf facts are fast everything is being computed fast except for in facts well you're telling me things that's not the problem the problem it's all this it's all this Loop if we can make this Loop faster we make everything faster huh well I mean now we can even talk about cash no it's not no enough the problem is all this loop it's not it's not the fact that those things are cash issues uh that number squared won't fit in a want Loop to a for Loop [Music] um I mean I don't know at this point like I don't know how this comp pilo works we can unroll this whole thing I mean I guess there could be Branch Mis predicts here and we don't really need that uh we know exactly what I'm upset that there's so many ones in this [Music] see all the ones they're very upsetting it Fe a power of two yeah and that's exactly what this is we multiply by that that's all that okay don't need that that's fast there's a chance this is faster that's not right okay wait now more of them are failing okay well we've learned that C++ 14 is faster than C++ okay let's look up hacker rank CPU timeouts H submissions leaderboard discussions okay look at how much time I get in go don't make me rewrite it and go I will it goes just as fast to see it's so unfair multithreading is all all oh CPU time would account for all thread execution time writing State information to a file can I really generate it all once unfair oh oh you know what I mean it's not much but it's a little more cash coherent guys see that tiny change and now only three of them fail pp1 if pp1 for in what fuck I'm so close I know we're so close Okay so we actually don't probably have to do that we can probably just say zero still like End Time stuff it's not fair okay I have one last idea and there's no way I'm actually giving up but we'll call it a last idea we have to rewrite this in C I will rewrite it in go if that's what it takes because I have 4 seconds in go which is really unfair is how your code say I don't remember expected expression before eight um cool oh different ones fail okay um does this still give the correct answer that'll help with cash no gives the wrong answer I mean technically we don't need the ram we could cast them we could cast them whenever we do a multiply dra precompute and one array instead of three that's not faster I'm focused on this loop it's doing uh 32 but still that's all of one I'm calculating factorials insanely fast like there's no faster way than that it's cash coherent like the only thing to really tweak here is this it's nicer anyway so should probably leave it like that the caching shouldn't really matter I have enough RAM wants to rewrite it and go okay I mean we can try want to inline the functions hate that it comes down to this but maybe compiler should be smart enough to do this though two two left faing two left all right um that's not going to make it faster just think it looks nicer it's really fast Civ it could be any of these functions it should be all in registers the only thing I'm thinking about here is a branch mispredict like I could write that out multiply because it does have a fixed all right should should we just do that I think that's going to that's going to bring an end to this um python shell online okay while n greater than zero uh if n print resal res time x run oh oh did I mean to put parentheses around my shit I guess I did all right we're just going to hard code no no no no no stop stop stop stop stop that's not what I meant to though uh let's call it y so it has the same name now let's go there with that why uh is that allowed in Python I forgot print x equals x * X Mod remember we can also hardcode this number okay uh we definitely don't need that last x x x all right who's ready to bring this to an end oh of course need some semicolons does everyone see what I'm doing does everyone see how this will end things hopefully come on come on come on you're going to work you're going to work what no that can't be no come on oh that's bullshit oh man that's bullshit I don't even how that's so unfair if look look at how o of one it looks it's so 0 of one and that's definitely staying in the iash there's no more branches is [Music] there oh I guess this is a branch I guess I could figure out how to fix that I think I can actually just fix that fact 0 equals 1 does that fix that I think I have to deal with INF fact zero as well I just might fix that let's see if it runs okay we don't need that line anymore did that make it faster I worked really hard on that can do it without primes try and C++ 14 okay I mean the nice thing about C is it's valid C++ I don't know is this even being compiled with 03 or something is there a way to get pragma 03 is that going to work they tell me what language they use right JC say oh those are different ones that failed pragma for faster GCC they're different ones that fail like it's so close no inputs not the bottleneck I don't know this thing seemed to not help if anything that was faster guys this never was supposed to take this long this was supposed to be a little warmup I was going to sit and read today but you know we I don't need two for loops on line 86 I don't have a line 86 so I don't know where you're looking here I need two for Loops here 31 32 2 34 okay now more of them fail we liked that okay you know what it's kind of bullshit but let's do it let's this will do half as many M facts it's two factorial still is that right is that right wrong answer okay I'm looking at you I * I in Ares where is that stuff not is this not correct I * i instead of I * 2 is that true all right I'll believe you guys and I'll think about why it's true after we win now I can make in fact twice as fast pretty easily with some shit so we'll try that next why is times I correct don't pass y aarg yeah we don't really have to pass those Zars either that's a good point give up on any hope of that working so close so close so close okay let's let's let's think more about this does this stuff not make sense we'll do all the odd ones oh is that the problem no it's not the problem because it didn't even work for small ones too many arguments to function power well yeah of course undefined reference to power I break it why is inline broken or something almost seems like a compiler bug okay wrong answer I mean this certainly works right yeah so why is that not right put in fact back in the first Loop okay all right chat we're going to try listening to you guys wrong answer oh because it's so close it's so close I OB has crashed I don't know guys it wasn't even my internet we're so close let's just try O2 sometime O2 is faster come on wait how did those ones fail a cuz we oh two I don't know wait did it die again I don't know oh no I think I'm just not playing it's back all right let's let's put some music on I good plan YouTube chill Beats [Music] okay okay what why is this wrong [Music] [Music] [Music] [Music] oh because that's not how factorial Works crap okay okay guys I have a plan I have a plane and we're going to solve we're going to just solve this I know what it is I know what it is okay we're going to invert every number we're going to invert every number we're going to create one more array we're going to call it inv num sub big okay now we're going to invert every number in Num sub I equals power sub I now instead of I we just do in Num subi does that make sense okay it's right okay that itself might still be too slow so we're going to use some cool speed up tricks this is too intense I I can't I can't do the music right now guys I can't do the music we're going to solve this we're so close so close to Great Victory okay 0 equals 0 1 equals 1 I think there's actually also fast ways to get them all I think there's actually fast ways to do this but I don't know them off the top of my head but I do know this is gonna work let's just see it might be fast enough you see what I mean now we're Computing in fact exactly like the other one is that a timeout or is that a wrong one one one left boys one left no don't worry I know how to make this fast I know how to make this fast um [Music] that'll make it twice as fast for got a semicolon is this it is this it is this going to be it let's go let's go let's go come on okay wait wait a second wait a second no no no no no no no no this is just random now fine I I I'll write the generic version of this if I have to no it's only easy for powers of to I'm not deal with that hang on can we think for a second about what multiplication [Music] is there's like a way to just katuba multiplication I don't know what that is get rid of all the prime code what what do you mean get rid of all the prime code just try it again it's G to work this time come on come it's different one I've had all of them pass no forget katuba whatever there's a way that's fast that is what it is I don't know why why is I * I correct oh I guess cuz We're looping up to the of 1 so that has to be iusus instead of i++ where this might just be slower from a cach perspective because we're doing these are random accesses now might actually be slower we only use it there different ones fail compute all numeric inverses in field all right all right all all right we're trying we're trying the pragma I don't think I can unroll any Loops it's a completely different set that fails that shouldn't matter I I don't know what can be a const exper do we have to rewrite it and go see like wait let's think we're actually just looping through all of these numbers one no that doesn't help us doesn't help us at all preash all inverses okay well we can try we can remove this Loop I think we can do this you know they get you your hopes up okay C++ 14 it seems to not make any difference I don't push options even really does no I I don't think it matters I think we just like keep resubmitting and eventually it's going to work should we switch to go I mean this is almost go isn't it what would I have to change wait a set of discs is numbered there are 25 prime numbers below 100 so get rid of the Prime function no the i++ and Plus+ I is not changing anything unless unless for some reason they're not optimizing the code at all I mean okay I have an idea Cash go here and say have you seen 30 and 36 fail before I equals 3 um good point you're right it doesn't matter but you're right go back to pseudo code and try rethink it from another angle I yeah okay we'll add back in unroll Loops I don't think it matters um for i = n iusus okay all right Fair Point fair point where okay all right you want this to be tary I I it should be the same yeah I'm sure there's very clever ways to do all this but we're so close like I've seen every test pass just not in the same the same run okay you love my all right you all happy with Turner let's go come on come on come on come on this time this time this time yeah Bo oh Turner is worse Turner really doesn't do anything different I don't think hm no now there's a more generic way to do this right so so we can do this like we really only have to compute them for the primes not even the odds right and that power function is slow subtract n from p in the Y Loop which y Loop yeah no it's everybody else on the machines these are shared machines this is unfair well I don't think you can yeah the only way to do that is really with that it's slow but there's not another way [Music] uh I don't really see inline assembly helping compilation error that's new oh did I leave some crap yeah I love some crap okay let's try [Music] this I didn't not mean to do that approximating the factorials the factorials are so this is O of n two of them fail I mean this might make things better now I'm willing to do it because this is using half the uh use less Ram oh yeah you got to get that cash nice oh we did it oh my God it's a all fucking day woo thank you for being here with me you were all real Bros ah hope you enjoyed look we we did you know I thought like oh yeah let's just find a little harder problem oh it's going to be medium oh how hard could that be did I miss up Mom yes did I miss some bullshit you guys all looked at the solution woo ah oh yeah let's share it on Twitter yeah I'm just going to copy and paste it no no no we're not running it again I don't talk about that no no no no no I think it actually got a lot faster cuz look at what we did we change these to ins um we Chang these to ins instead of Ms so it used half the ram but it's not about the RAM usage it's about the size of the cash right oh oh you going to wash my hands for a while it's over it's over we did it oh yeah yeah oh first you got to scrub with like 30 seconds soap his H washing stream oh yeah that's nice that's nice that's too much soap on my hands oh we're we're going to cook some eggs yeah whip up like a triple egg omelette some scouting onions I'm going to go read my friends coming to visit me tonight everything is good everything is good I'm really glad you're all here with me no Minecraft no cooking it wasn't this this this I just when I'm on stream I can't give up I never want streams to end failures Bitcoin thank you for subscribing thank you oh this is going to get mad views oh we got mad views on this channel worked real hard today uh no I don't know all right thank you thank you imagination the truth is guys I'll tell you one piece of advice for life and I'm not going to tell you all where I learned it from and it goes like this never give up never surrender uh no it's from Galaxy Quest it's a good movie you guys should watch it all right see youall later never give up never surrender all yeah I got to got to I got to I got to look what no I didn't mean to move that one a no yeah okay right there yeah nope no I'm moving the wrong one no no now want to move that one yeah oh yeah all right see you later