all right hi everyone welcome back to the channel for those of you who don't know me my name is prian Agarwal I am a candidate Master on code forces and a six-star coder on COD Chef I also recently got India rank one and Global rank six in Google Kickstart round a 2022 so in this video I'll be talking about you know the topics that people should be doing in order to reach 1600 rating on code forces and there's a very strong reason as to why I making this video uh recently I released a poll on this channel wherein I asked people to tell me you know uh what rating range do they lie in on code forces and I realized that almost 91% people on this channel are less than 1600 rated so that's like a huge number right uh and that's why I'm making this video wherein I won't be just talking about the topics that you should do in order to reach 1600 but I'll also be talking about the topics that you know a lot of people less than 1600 are currently doing but they should not be doing so I've seen that a lot of people in competitive programming start learning really Advanced data structures and algorithms uh that you know they might never be able to actually use in a contest so I you know firmly believe that if you're learning something uh you should learn it only you know when you think you can apply it right so for people who are less than 1600 rated uh if you're learning DP optimizations let's say then uh there's a very high chance that you'll never be able to use them in live contests right so uh that is one thing that I'll be addressing in this video and this is something that will be there at the end so I suggest that you watch the complete video and uh there will be a lot to you know learn from this whole video so yeah without any further Ado let's get into the topics that you should do in order to reach expert now even before we start talking about the topics ICS that you should do there are certain prerequisites that you should have so you should be really familiar with one programming language be it C++ Java or python you should also be familiar with C++ STL or equivalent uh for example in case of java it could be Java collection framework now let's say you're done with C++ or let's say another programming language and you're also done with C++ STL or some equivalent what next you should have also solved around I would say 100 to 120 problems combined on all of the online judges uh maybe you could have done 30 problems on code Chef 30 on code forces and you know maybe 20 on at coder uh I just want that you know you don't get into that phase wherein you start learning topics even before your competitive programming Journey has uh you know started right so it is very important that initially you solve a lot of random problems so that you get to know how online judges work things about time and space complexity uh you know uh how the leaderboard thing works how point system works in contexts so these are certain things that you should know even before you start learning topics right uh so yeah uh with the prerequisites you know aside let's talk about the real topics that you should do the very first topic that you should do is number Theory you should try to Master number Theory as this is kind of the most important topics for beginners in competitive programming so I've listed down a few subtopics that you should try to do here the very first topic is modular arithmetic uh the next topic is basic knowledge of primes multiples devisers right for people who are already in their college uh I don't think you need to focus on this a lot uh because this is something that is covered till you know High School level so you should be pretty uh you know efficient with this the primes multiples devisers part the very next thing that you you should be really familiar with is called bitwise operations uh bitwise operations are like you know operators like and or zor nand and you know stuff like that so there are quite a lot of properties around these bitwise operators itself so you should try to you know Master bitwise operations just after you have some knowledge of primes multiples and devices the next topic that you should do is ukan algorithm this is a really important topic and ukan algorithm will also teach you you know how to calculate the gcd or the hcf of two numbers really efficiently right so the next topic that you should do is called SE of ostanes uh this is a concept or I would say an algorithm that you can use uh to you know find all the prime numbers from 1 to n the next thing that you should do is called binary modular exponentiation let's say I tell you that you have to find out 2 ra to the power th000 modulo some number so in order to do this efficiently there is this thing called binary exponentiation that you can read about right uh after you're done with binary exponentiation the very next topic that you should do is combinatorics right combinatorics is is really very important even for very Advanced problems combinatorics is something that you should try to master so these are certain you know topics that you should do in number Theory talking about resources you can refer to this channel called code and code uh this is like a YouTube channel and they have a dedicated playlist on number Theory and I can tell you from my own personal experience that this is one of the best resources that are there uh you know for number Theory apart from that if you like reading blogs I would suggest you to you know refer to this website called CT algorithms uh you can refer to the algebra section of this website and it contains a lot of you know techniques and uh Concepts around number Theory and apart from that uh you know I saw a latest video by utar Gupta which is there around number Theory you can watch that as well all right moving on to the second most important topic this is binary search and tary search uh now again tary search is not really that important for people who are less than 1600 rated uh but just in case if you're learning binary search I would recommend that you know you also give a look to Turner search and you know try to understand what happens there talking about binary search the very first thing that you should do is to learn about General binary search when I say General binary search it is just referring to you know finding out an element in basically like a sorted array then you should learn about monotonic functions the primary reason why you should learn about them is because you can use this technique called binary searching on answer right binary searching on answer only works on monotonic functions so when you're learning about these type of functions you should also be able to prove that if you are given a problem you are able to convert it to a form that has a monotonic function right and you should be really good with proving that the function that you're forming is actually monotonic right after that you should be familiar with certain C++ STL functions like you know lower bound upper bound binary search because these are certain you know functions which you don't have to implement on your own they are already available for you so if you know how to use them it will be really very helpful for you in context now coming on to turn search I would first of all recommend you to learn about convex functions right what exactly is a convex function this you should be knowing because the thing is that tary search only works on convex functions then coming on to turn resarch once you're done with convex functions learning about Turner resarch is not a very big deal uh you can understand the very basics of Turner resarch and just in case if you have to apply it in a problem uh you will be able to use it so I haven't seen a lot of advanced problems on turn search so even if you learn the very basics of it you should be in a good position talking about the resources for binary and turny search first of all you can refer to this beautiful tutorial on code forces edu section uh so code forces edu section is like a small section on code forces and it contains a lot of tutorials on really good you know topics in competitive programming uh and binary search is one of them and these are certain tutorials that are taken up by one of the grand Masters on code forces right and in case you want to do binary search really very quickly in you know like 1 to 1.5 hours then you can definitely refer to one of my videos on this channel which is uh specifically on binary search if you want to you know learn about tary search I would recommend referring to this website again called CP algorithms uh this contains a really good blog on turny res search and it not only contains the concepts on turny search but it also contains a lot of practice problems on it right so I have seen that uh you know there are not a lot of publicly available problems on tary search so you can definitely refer to this blog on CP algorithms and you can maybe you know try out the first two to three problems on T resarch and you should be good to go with it the very next topic that you should focus on is called greedy uh when I say greedy I am referring to greedy algorithms basically so in order to be really good with this topic first of all you need to solve a hell lot of standard greedy problems right so uh you might as well you know uh go on court forces and solve a lot of greedy random problems uh but I don't think for beginners that is like a really good approach so when I'll be talking about the resources for greedy uh I'll be you know specifically telling you as to how you can practice these standard problems right uh moving on uh you should first of all uh you know not only be just solving greedy problems but you should also be able to prove your solution right proving is kind of the most important thing when it comes to greedy because let me tell you when you look at a problem there might be like 10 greedy approaches that come to your mind uh but you know almost like eight or out of them will be wrong right so if you you know get on to actually prove your solution then only will you realize that you're actually making some mistake right so if you see uh you know people attempting contests I've seen that a lot of people make a lot of wrong submissions on like the very first few problems uh the very first few problems in every code forces or Cod Chef round are supposed to be really greedy in nature right so it is very important that you understand how to prove your Solutions right you might at times rely on your intuition but uh before you actually prove your solution I don't think you should uh you know be committing the problems right so in order to be really good with proving Your solution you might as well look at this thing called exchange arguments however this is kind of really optional uh even if you don't know a lot about exchange arguments you can prove your Solutions you know easily when it comes to problems that are less than 1600 rated right after that when it comes to actually solving problems I would highly recommend trying out you know the searching and sorting section of CSS problem Set uh you can do the first 50% problems on this problem Set uh of the searching and sorting section and you will be really good with greedy because this contains a lot of standard problems and some standard techniques that you should know talking about the resources for greedy again uh first of all if you have to solve a lot of standard problems then there is a dedicated section for it on Geeks for geeks uh you know something like uh something titled as standard greedy problems and I'll leave the link to it in the description so when I was you know learning a lot about greedy I referred to this one section and this really helped me coming to exchange arguments I had referred to one of the videos on this channel called you know algorithms live so this contains a really cool uh tutorial on Exchange arguments so I'll leave the link to that also in the description and you guys can check it out uh talking about uh practicing problems you can refer to CSS problem Set uh you can again solve the first 50 problems of this section on the searching and sorting section and you'll be good to go right now before we move ahead let's talk about the sponsors of this video which is Geeks for geeks Geeks for geeks has come up with a really fun virtual event called geek summer carnival the pre-event of this Carnival will be happening from 26th March to the 2nd of April this event will be filled up with fun excitement and entertainment and a lot of games related to coding and there will be loads of goodies and discounts on various Geeks for geeks courses that you can win throughout the carnival days you can even check out their wall of wishes section wherein you can fill up your details and wish for a course that is there on Geeks for geeks and if you're lucky enough you'll get the same course for huge discounts or even for free in case you have any other doubts you can check out their FAQs and uh you can check out the whole event with the link in the description moving on to the fourth important topic that you should do in order to reach 1600 it is called dynamic programming right this is a really important topic when it comes to competitive programming or even interviews and coding tests right so this is one topic that you should Master even if you don't want to reach 1600 you should Master dynamic programming right how do you start learning about DP first of all you need to be very good with recursion and backtracking once you are familiar with recursion you can learn about memorization in recursion itself right so what happens in memorization is that when we are running some recursive algorithm uh there are like a lot of you know overlapping sub problems that occur there so when we have the answer for an for a sub problem we should not calculate the answer again for that sub problem right so that's exactly what dynamic programming you know helps us to achieve it just stores the answer of a certain sub problem and whenever we require the answer for that sub problem it just returns that you know without even calculating it again right so let's say now you're done with recursion and backtracking you also know about memorization what now you need to now solve a lot of standard DP problems and how you can do that you can refer to this DP section of CSS problem set again uh you can try completing I would say 60 % problems from here and you should be really good with DP now you can learn some basic ideas about DP with bit masking some basic ideas about DP on trees you don't have to go a lot into the depth of DP onent trees and DP with bit masking but initially if you you know learn it to a level wherein you can solve problems that are I would say, 1600 or 1700 rated on code forces then you should be really at a very good point now there is just one more point that I want to talk about which is that you should not be very you know specific about learning how to write iterative DP at this point when you're less than 1600 rated because trust me if you I mean if you are comfortable in iterative DP that's the best way to go about DP right but if let's say you're not comfortable in iterative but you're very comfortable in recursive so there is no need to uh you know waste a lot of time and learn about iterate to DP because at this point I don't think you will ever require things like space optimizations or maybe state optimizations right so if you don't require that then recursive and iterative are pretty much the same fine so if you are you know really tensed about the fact that you're not very good with iterative DP then it's not at all a big issue you can manage it even after you you know reach 1,700 or maybe 1,800 on code forces right so talking about the resources for dynamic programming you can start with erto's uh you know DP videos on uh his YouTube channel so he has around I would say uh three or maybe four videos on dynamic programming and all of them are very beginner friendly so you can check that out uh then for practicing problems you can refer to CSS problem set and add Cod DP contest uh now mind you again you don't have to practice all the problems from CSS problem set or all the problems from atca DP educational contest uh from CSS problem set you can uh try out the first 60 to 70% problems for atcoder DP contest again you don't have to try out all the problems you can try out I would say the first 10 problems on atod DP contest and you will be in a very good position to tackle a lot of DP problems right now you might get stuck at you know uh problems in CSS problem set and atod DP contest so for CSS problem set you can refer to Karthik arora's DP playlist so he has compiled like the solutions for almost all the problems on CSS problem set and apart from that he also has a lot of Tut tutorials on stuff like digit DP and you know uh DP with bit masking DP on trees so you should definitely check out his channel specifically for dynamic programming right for atcoder DP contest you can watch utash gupta's atcoder DP playlist so he has covered a lot of problems from this atcoder DP contest and uh once you do all of this you will be in a very good position to tackle a lot of DP problems and let's say you're done with all of this I would then recommend you to try out uh problems that are uh almost 1,700 or 1,00 rated on code forces right just random problem solving on DP right so moving on to the next topic uh now let me give you a disclaimer uh all the topics that I'll be talking about from this point uh will not be very helpful for people who are less than 1400 rated so if you're less than 1400 rated I would advise you to take this with a pinch of salt don't uh specifically go a lot into the details of the topics that I'll be discussing from this point right but if you're uh kind of like at 1,400 or above that then you can you know do these topics so yeah let's move on to the next topic which is called trees right so how do you do trees first of all you need to cover the basic properties of trees you need to understand how you know the structure of a tree looks like uh what exactly is a rooted tree what exactly is a non-rooted tree then you know what is a parent a subtree a child an ancestor things like these right so there are like a lot of properties then you can learn about DFS on a tree right uh and I can tell you from my own personal experience that if you are done with the basic properties of trees and the DFS uh you can solve almost 90% of the problems that are less than 1,700 rated on code forces and I don't think that for people who are are uh kind of aiming to reach expert you need to be solving problems that are 1900 rated or 2,000 rated on trees right uh but yeah so if you're done with basic properties and DFS you will be in a very good position after that you can learn a little about binary lifting so this is like a very you know important topic in trees uh you don't have to go into a lot of details about binary lifting you don't have to solve a lot of problems on binary lifting uh but a major application that you should look at in binary lifting is finding the LCA in order of log and time like basically finding the LCA of two nodes what is LCA LCA is lowest common ancestor right uh when it comes to practicing problems again you can refer to the tree section of CSS problem set fine so yeah these are the certain uh subtopics that you should refer to in trees uh you can also do DP on trees but uh I think uh once you're done with trees that is the point when you should actually do DP on trees so I had sort of listed DP on trees in the dynamic programming section only but I would recommend you to first of all go through trees and then only you know go into the DP on trees or even if you have to go into DP on trees then first of all cover the basic properties and the DFS part of trees and then go into it uh talking about the resources for trees first of all I do have two videos on my YouTube channel on trees uh the very first video covers the basic properties and DFS uh some basic ideas of DP on trees as well and the second video covers you know uh Concepts like LCA and bandary lifting right so you can check out both of these videos and apart from that if you you know want to uh have a video wherein somebody solving problems and you can solve problems along with them then you can you know watch gin Colin's trees uh topics stream you can also refer to erto's Binary lifting video uh which he has on his YouTube channel so this was like a really cool video that I you know watched a long time back so yeah you can refer to that as well and uh for solving problems again you can you should refer to CSS problem set fine you should try to solve at least I would say uh seven or eight problems from the tree section uh once you do that you will be in a very good position again and you can maybe try out 1,600 and 1700 rated problems on code forces after you're done with all of this right moving on to the sixth and the last topic for this video which is graphs right so you should be doing graphs at not a very high level but up to an intermediate level in order to reach 1600 so you should again start with the basic properties like what is a cycle what is a path uh how do you do a DFS how do you do a BFS on a tree so these are certain things if you do these uh you will again be able to solve all problems that are uh kind of less than 1600 rated on code forces you can also look at Connected components and also some basic ideas about directed graphs right so I'm not going a lot into the details here because I again don't want you guys to go a lot into the details of graphs so there might be a lot of people who might reach expert even when they don't know anything about graphs after learning some Basics about uh the directed graphs you can you know learn about minimum Span in trees so you should at least know one minimum span inry algorithm and you should be able to code it up you might as well you know learn prim's algorithm or maybe csal algorithm but uh the idea about csal algorithm is that you should also be familiar with disjoint set Union so this is why I mentioned disjoint set Union as you know an optional topic if if you're able to do it well and good then I would recommend you to you know learn cral algorithm for minimum span inry but in case you are not familiar with disjoint set Union then go for prim's algorithm okay talking about the resources for graphs again you can watch gon's topic stream this is like a really cool video around 3 to 4 hours and it contains a lot of really standard problems right uh but again uh you should not watch this video when you're just starting out in graphs right instead you can watch William fet's graph playlist so this was something that I also referred to in my time when I was you know learning a little about graphs so this is not something that will contain a lot of problems but it will contain a lot of theoretical Concepts right so even before you go on to Valen Colin's topic stream you can watch William facets graph playlist and again if you want to solve a lot of problems in graphs you can refer to CSS problem Set uh try out around the first uh 10 or 12 problems in it and then you can you know get into code forces and do random problem solving till I would say 1,700 uh rating right so that's pretty much it for graphs all right so now that we've talked about the topics that you should do let's now talk about the topics that you should not do now it's not like that if you do any of these topics you will not reach 1600 you might as well reach 1600 even faster but the thing is that if you waste a lot of time on any of these topics uh you will be missing out on uh you know the time that you could have spent on the essential topics that I just discussed right so these are certain topics that you should not do uh at this point if you're not very comfortable with the first six topics that I had listed till now starting with Advanced number Theory there is no need to go for topics like Oiler toan function and you know Matrix exponentiation and there are like a lot of advanced topics in number Theory uh like Chinese remainder theorem and stuff like that even extended ukan algorithm I don't think there is any need for you to do it at this point right if you reach expert at that point maybe you can try these topics but right now I don't really recommend any of these topics now talking about range query data structures uh I have seen a lot of you know uh beginners right now learning about segment trees F victories trust me there is no you know use of learning segment trees penies at this point you will never be able to use segment if you're only solving problems like ABC code forces ABC once you start solving problems like d and e that is the time you will require segment trees but by the time you are able to solve D problem you would already be above expert right so there is no need to do segmentary saries right now there's no need to waste time on that again don't do tries right there is no need to do binary tries or like General tries uh which are used for string uh like matching algorithms and like string searching and again no there is no need to do Advanced string algorithms you can learn about hashing uh but that's it there is no need to learn about stuff like amb algorithm Z algorithm or maybe maners algorithm again don't do strongly connected components I don't think any problem that I've solved on strongly connected components is like less than 1700 rated right so there is no need to do that and it is like a really rare topic so once you get to a very good rating at that time you can do strongly directed components and you will also be you know finding these problems uh quite frequently when you are at higher rating right uh and then there are certain you know Advanced tree algorithms like uh Oiler T heavy light decomposition and centroid decomposition I mean I can tell you from my own personal experience I have like absolutely close to zero idea about heavy light decomposition and CID decomposition right uh then there are like uh things like square root decomposition again there is no need for you to do that uh there are things like Mo algorithm and you know a lot of other stuff in square root decomposition so there is no need for you to do Square decomposition no no need to touch it right and the last thing is d optimization so I have seen quite a lot of you know people recently who are coming up to me and talking about you know things like digit DP maybe or higher Advanced you know optimizations like convex cell optimization trust me there is no need for you to do any of these topics uh if you have to reach expert uh you will reach expert by just knowing the basics of DP even if you know like the very basics of DP with bit masking DP on trees that much is sufficient there is no need for you to do any DP optimizations right so these are certain topics I mean these are certain common topics that I've seen people doing uh at this point when they should not be doing these topics right so don't touch upon any of these topics uh I can assure you you will never find any of these problems in you know the first I would say the first three problems on code force and most of the times even on you know even the D problem won't be requiring any of these topics right so yeah that was about the topics that you should not do so yeah that is it for this video guys I hope you all liked it and in case you did don't forget to smash the like button below and in case you're new to this channel then don't forget to subscribe to it because I do post a lot of content around competitive programming here and yeah obviously in case you liked some parts of the video or in case you did not like some parts of the video then be sure to comment Out Below and let me know your feedback because then I can plan out more content accordingly so yeah in case you guys would like to uh follow me over other social media platforms then yeah I am really active on Twitter and a little active on Instagram as well right so yeah that was it for this video and I'll meet you in another one so yeah till then bye-bye