Computations Modulo P in Competitive Programming
Рет қаралды 123,447
4 жыл бұрынTutorial for beginners on computations modulo P in competitive programming. In so many Codeforces problems, we need to print the answer modulo M, most often M=10^9+7. What's the reason for that and how should it affect your code? Why modular subtraction is tricky and division even more difficult (modular inverse uses this en.wikipedia.org/wiki/Euler%2... Watch the video, then solve introductory problems here cses.fi/problemset/ and read Competitive Programmer's Handbook for some structured knowledge cses.fi/book/book.pdf
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Github repository: github.com/Errichto/youtube
- Live streams on 2nd YT channel and on Twitch: / errichto2 & / errichto
- FB and Twitter: / errichto & / errichto
- Frequently Asked Questions: github.com/Errichto/youtube/w...
#Coding #Programming
@abhishek.rathore 4 жыл бұрын
You are developing a lot as a Content Creator. I love that. Also that new background looks dope.
@BuciuEmilian 4 жыл бұрын
I agree. He definitely evolved a lot in the past 6 months as a content creator. I also like that some of his videos get humorous.
@mdisrafil2491 4 жыл бұрын
Soon you will get 10^9+7 subscribers
@zinyang8213 3 жыл бұрын
% M :D . Thanks Errichto, your content has been a godsend blessing :)
@aniketash4738 3 жыл бұрын
@Kane Sonny you have to give money right ? in instapwn i tried they were asking to pay money
@keshavbansal6343 5 ай бұрын
He had more than a billion it just got modded
@sayanghosh6996 7 ай бұрын
these videos packed with valuable information are way way better than the 'influencer' videos by other channels which dont actually help you learn anything. Thanks for this!
@lucasnogueira3232 4 жыл бұрын
Errichto youre amazing, your youtube channel is the best in cp
@PankajKumarGladiator 4 жыл бұрын
Appreciate your explanation on modulo operations. This will definitely help me to solve problems with more precision. Expecting for more future lectures like this. Keep it up !! And nice background 👌
@user-he4st2ro5h Жыл бұрын
Guys, I think we should really appreciate these brilliant pieces of knowledge and experience which the man shares with us. Thank you so much, Errichto
@farazamir-mi7et 5 ай бұрын
GOOD saying I also love that best of luck
@vms_kt 3 жыл бұрын
Thank you very much for the explanation. By far the easiest one to understand why and how to implement the modulo in coding contests.
@shresthmishra9329 4 жыл бұрын
For those who only want to know about how modulo works with division or inverse can directly skip to 10:50. Thank you @errichto for investing your time and making us understand easily.
@divyanshu8874 3 жыл бұрын
Besides you are such acclaimed programmer, You are so humble and simple❤️❤️
@GameplayForNarration 4 жыл бұрын
this is awesome errichto😃. it’d be cool if you made videos like this on other topics from the competitive programmers handbook, or just books in general. 👏🏻
@deeptendusantra670 4 жыл бұрын
Your explanation of codes is very insightful.Loving your content.♥️
@nextrie 4 жыл бұрын
Once again, I learn something new from you. Thanks so much.
@RamisaAnjum 2 жыл бұрын
You look pretty relaxed all the time! It inspires me to learn more and more.
@nelsonthekinger 3 жыл бұрын
I only saw this requirement once in a question, it was today and i was confused. This video helps. Lot! Thanks!
@arinroday302 4 жыл бұрын
Just keep it up Errichto. Excellent as always
@society183 3 жыл бұрын
I hope to see u doing more of these educational topics as these are easy to understand and learn...
@aryankumar87771 Жыл бұрын
genius man, they way of ease of explanation is unparalleled on yt
@williamwambua7710 4 жыл бұрын
Thanks ....Errichto this site has every thing organized
@adityasoni6966 4 жыл бұрын
Great Video!! Waiting for the PART-II.
@TahsinAhmed-yj9ns 4 жыл бұрын
to the point video, need these videos more , as always great content
@vaibhavjadhav8987 3 жыл бұрын
This guy really deserve Millions of subs💯💯
@shaswatlenka1416 3 жыл бұрын
How in this world are you so composed all the time! That's something we all need to learn!
@parthsalat 3 жыл бұрын
Very true!
@sourabhjagtap4950 4 жыл бұрын
Very nice explanation !! Keep on doing what you do, and thanks for sharing !!
@shaswatlenka1416 3 жыл бұрын
Keep making awesome videos! Love these!
@simone8504 3 жыл бұрын
This helped me a lot with modulo operation, thank you very much !
@kimjong-un4521 3 жыл бұрын
we are so lucky to learn from you.
@praveenawesome2182 4 жыл бұрын
Thanks erricto for such awesome content being a pupil on codeforces ,these videos motivates me to do a lot better and try to jump to candidate master one day !!
@thamidurandilbandara415 2 жыл бұрын
you can do it! best of luck! ( i am also trying :D )
@pallab900 4 жыл бұрын
Thank you for this. This lecture was very enlightening
@bhaaratkumarkhatri4834 3 жыл бұрын
u r geniusssssssssssss bro thuanku............. i am stuck at the problem from 4 days ................it is solved nowwwwwwwwwwwwww
@ashutoshsanodia5690 4 жыл бұрын
Very valuable info errictho
@abhishektangod657 4 жыл бұрын
I loved the new background 😍
@lovvyparhar393 4 жыл бұрын
loved the new background!
@karimfathi1955 3 жыл бұрын
this is very useful for beginners competitive programmer , please make a lot of videos for us.
@Grassmpl 3 жыл бұрын
Z/nZ forms a ring with the natural addition and multiplication of cosets well defined. If n is prime, we get an integral domain which make hashing very convenient especially with double hashing with a constant secondary hash function.
@jimwoodward7293 4 жыл бұрын
Great lecture -- great content!! Thanks.
@mihirbhasin1970 4 жыл бұрын
Bro you are such an inspiration to me ❤️
@akakop 4 жыл бұрын
@@audiogear4412 what are u getting from benq and 7k+? Atleast this guy is doing something for u.
@audiogear4412 4 жыл бұрын
@@akakop My bad.
@akakop 4 жыл бұрын
@@audiogear4412 np
@creativegiant148 3 жыл бұрын
I liked when you said we should try to make languages equal in cp. I feel this problem a lot in cses i do it in java and its real hassle over there i need to 100% optimize my code to get selected, while the same less optimized algo work fine in cpp When i tried to tell this thing in one of cf blog everybody criticized me and they all devoted(so now im a newbie with -5 contributions) but now i feel lit good
@subham-raj 4 жыл бұрын
I wanted this from so long :)
@Crytoma 3 жыл бұрын
long long*
@sanchitchakraborty8146 3 жыл бұрын
You really are keeping me motivated
@harshit.jindal 2 жыл бұрын
Great explanation. Thanks a lot. Subscribed!
@luanaamorim5055 3 жыл бұрын
Your videos help me so much, thanks!
@harinath_mishra 3 жыл бұрын
This was very great video errichto sir .I would love to watch your video Editorials of Contests.
@arthak2475 4 жыл бұрын
It's so good to see that you recommended CSES Problemset. Cause I did say that in one of the comments that sent you, feels like i recommended it :p Great Video btw.
@Errichto 4 жыл бұрын
I know CSES problem set from an announcement blog on Codeforces... where I then complained about too many websites and said this is unnecessary :D
@arthak2475 4 жыл бұрын
@@Errichto I know that you must have already knew about it.
@arthak2475 4 жыл бұрын
@@Errichto Everything must seem unnecessary when you're at a level that you're at. 😬
@abhishekshaw21 4 жыл бұрын
Your videos on April leet code challenge were amazing kindly do it again for June.
@katakamsaiteja7934 3 жыл бұрын
your content is gold.
@Errichto 3 жыл бұрын
Thank you :)
@dinohunter7176 3 жыл бұрын
I managed to follow the logic, but unless I don't try it in coding, I'm not confident I've understood perfectly. Thanks for new insight of hacking numbers faster.
@prashantkumar2963 3 жыл бұрын
Thank you Errichto.
@abdelrahmanyehia562 2 жыл бұрын
This was very helpful!! Thanks you.
@tirthjayswal9895 4 жыл бұрын
Best Explentation on MOD ..Thanks
@mokshchadha9151 4 жыл бұрын
you are awesome errichto maybe someday i will be a better coder too, keep making such lessons
@parthsalat 3 жыл бұрын
Thanks for the video. And oh, did I mention you are no less than a God?
@stabgan 3 жыл бұрын
This video was very helpful. Thanks
@manjunathvasam4981 4 жыл бұрын
There is this set of problems based on calculations involving doubles. Could you make a video on this if possible?
@mohamedtamer9041 2 жыл бұрын
Thanks. Good explanation 👏
@tomtan298 4 жыл бұрын
Awesome Video! I can see a great potential in you to be a awesome youtuber! Would be nice if there were slightly more tutorials on entry to intermediate questions and concepts used in CP.
@tomtan298 4 жыл бұрын
Or maybe a beginner - intermediate stream
@ashuadhana1840 4 жыл бұрын
@@tomtan298 this is actually one of the very basic things in cp , i think many people in cp may not even talk about it ,it's that basic
@AmitSingh-cs2hb 3 жыл бұрын
Nice explanation brother😍😍
@alferidmokhammed4958 4 жыл бұрын
Nice video! It would be nice if later you could cover more advanced algorithms like baby-step-giant-step.
@DinoOnBike 3 жыл бұрын
That background is soo dope
@miteshkumar3183 4 жыл бұрын
A topic you could make a couple videos about is Digit DP. There aren't many good explanations online about this. This is a technique to solve questions that involve counting numbers within intervals with certain properties. For example, Given to very large numbers as strings L and R, and an integer K, count how many numbers from L + 1 to R inclusive, that have exactly K non-zero digits.
@parthsalat 3 жыл бұрын
For errichto, even coincidence is a power of 2
@bored9711 4 жыл бұрын
So nice man. Tysm
@xbaphomet0136 3 жыл бұрын
nice tutorial
@mizel_1121 3 жыл бұрын
All programmers bad teachers only Errichto he the best programmer and best teacher Always He said just practice so everyday I grow thank you bro I love you u change me forever ♾
@ztrixx3280 4 жыл бұрын
Simply Awesome
@algobear6816 2 жыл бұрын
Amazing , thanks ❤️
@occo5877 4 жыл бұрын
Please do leet code challenge June !!! You don’t need to put the video up the same day since you said it’s tiring. Pleaseeee! You r super helpful!
@RafaelGuiimaraes 3 жыл бұрын
Thank you for this video.
@abdellatif_anaflous 4 жыл бұрын
Keep going bro my eyes on u
@pranavgaur6399 3 жыл бұрын
Thank you this is really helpful
@udaypatidar5183 4 жыл бұрын
You are rocking us
@suryanshchaturvedi1391 4 жыл бұрын
Bro please make more videos on Mathematics. Keep up the Good Work.
@ChandraShekhar-by3cd 4 жыл бұрын
This has REVEALED the SECRET of (10^9+7) . I was always thinking that it is a random sort of fancy thing that all competitive sites are using. Thanks a lot Errichto for CRYSTAL CLEAR Explanation.
@darkcry69 4 жыл бұрын
We need a tutorial on graphs
@xlewusx 4 жыл бұрын
Super materiał :)
@AbhishekKumar-hj4qo 4 жыл бұрын
You are the best @Errichto.. many might have more knowledge but you are the one who shares it... And that differentiates you from others.... BEST OF LUCK FOR CODEJAM ❤️ #love_from_India ❤️
@saikatkarmakar389 3 жыл бұрын
I really liked your problem solving approach. Any tips on how to be a better competative programmer ☺️☺️
@em_nikhil_007 4 жыл бұрын
Exactly i was looking for it . Are you listening to my mind?
@sauravpandey599 4 жыл бұрын
A great fan of yours
@andrijaciric4661 3 жыл бұрын
Could you do editorials for the graph and math section from the cses problem set? It would be nice
@hackerencrypted8234 4 жыл бұрын
Hey Errichto, this was very basic introduction to modulus operator. I was able to learn this on my own when i was a super beginner.I ll be happy to see something more advanced something which troubles me a lot like using modulus to calculate inverses till n in O(n) time. I saw there was some tough formulae on that (a pretty long one) which i could not understand how it works. Your content is quite good for people who are beginning. But please for people like us who are stuck in ratings like 1500-1600 on cf , please add some intermediate stuff too, maybe some advanced DS too. Go on with your great work! GL!
@lawbindpandey402 4 жыл бұрын
Well he can't solve a specific problem !! So he teaches the basics and the later can be learned !! If you want the other way (specific problems) you can view his other channel errichto 2 where he does long stream !!! If lucky enough you might get solutions of some contest that you might be participating in, even the "F" problems !!! Any way you can always find editorials for standard problem !! And as you say you are 1500-1600 on c.f you'll be well good to figure it out yourself!! Just try for 2hrs max for "F" problems and you'll be there .....
@hackerencrypted8234 4 жыл бұрын
@@lawbindpandey402 i know that bro! I am not asking for solving specific problems.I am asking for some intermediate concept. Solving F is a bit too far for me. In div2 i usually do 3 out of 6.Where did i ask to solve some specific problem?? I requested for some generic intermediate stuff.
@hackerencrypted8234 4 жыл бұрын
@@lawbindpandey402 I am happy you replied, but please read and understand what one wants to convey and then reply.I used the word "like " which according to me suits when you are giving an example and not for specificity.
@lawbindpandey402 4 жыл бұрын
@@hackerencrypted8234 Aah!! got you bro !! Sry for bothering you ...😇😇😇...Any way it's always easy to explain some concept with litter example and so he did !!! and once again my apologize !!!😇😇😇
@hackerencrypted8234 4 жыл бұрын
@@lawbindpandey402 why you are apologizing dude! no way! its perfectly okay buddy!! I am from India doing my standard 11th right now! I have a lots of respect for you bud!! keep on with good work! Ciao Adios!!
@5590priyank 4 жыл бұрын
Which site you use to draw ? This one looks different than previous site but better!
@kimjong-un4521 3 жыл бұрын
Thank you.
@notabot8909 4 жыл бұрын
Do you recommend only reading the editorial and not implementing the solution in the hope of getting exposed to more ideas/problems? Or does it not matter at all? I read your FAQ and couldn't find this question
@googool.3769 3 жыл бұрын
Just wow ❤️
@Yash_Shende 3 жыл бұрын
TBH you are GOD in CP
@imranhossain6439 4 жыл бұрын
This video was really helpful.Can you upload graph tutorial.
@rajmittal5394 2 жыл бұрын
i am solving some question and there given modular division , i think that it is like a regular modulo but this is something new for me
@ZzwhiskeybkszZ 4 жыл бұрын
Curious what device you are using to write on the screen like that?
@amitrai6388 4 жыл бұрын
Thank You so much!!!!
@tusshar2000 4 жыл бұрын
For python multiplicative inverse can be calculated by pow(p,mod-2,mod)
@rishavmasih9450 Жыл бұрын
This stuff is a recreational drug.
@sharinganuser1539 3 жыл бұрын
I learnt the subtraction and division part the hard way...when I was implementing some rolling hash function....inverses can also be good... P.s I commented at around 9:00..I should have seen the whole video first..
@zqlimy 4 жыл бұрын
Thank you!
@RafaelGuiimaraes 3 жыл бұрын
You are awsome!
@systemflaws 4 жыл бұрын
Nice and Smooth explanation. I love your tutorials. One day, I will become a red coder. Give my 110% to this journey.
@saksham9170 4 жыл бұрын
I highly doubt it. Most people who become red love to solve problems rather than commenting on a video about becoming red.
@utkarsh.dsiddhpura9467 2 жыл бұрын
Plzz make more content like thiss........
@ashwiniabhishek1504 4 жыл бұрын
Can you make videos regarding permutation cycles problems. I am pointing towards the codechef may challenge problem TRPLSRT? Also can you suggest some problems similar to it albeit simpler.
@xssimposter5203 4 жыл бұрын
For those interested in the modulus calculus and the tricks he discussed with Euler's formula. I would recommend reading a cryptography book. You learn some clever tricks with prime numbers and modulus.
@xssimposter5203 4 жыл бұрын
Understanding Cryptography by Christof Paar has a great web series to go along with the book.
@AkashKumar-lr6hc 2 жыл бұрын
Best video
@juliocesarmamanivillena8943 3 жыл бұрын
excelente video, y yo buscando big integer en c++ jejejeje saludos