Roadmap to be Div1 at Codeforces!
This article is contributed by Bharat Khanna, Co-founder of Programming Pathshala, who has previously worked at Tower Research Capital as SDE-II.
In this pandemic year, a lot of students decided to upskill themselves during the continuing lockdown, which I think is a wonderful idea to prepare for the upcoming surge in requirements for Software developers.
I often get this question from them: “How to get high ratings on Codeforces/Codechef?” and “What is the correct roadmap to get Technical jobs?”. And a follow up question with this, is generally, “From where to learn DP, Graphs and Segment Trees from the overwhelming content present online?”.
If I ask them their current ratings, most of them are either unrated or are currently a newbie, a pupil or in some rare cases, a specialist. So for all such budding coders, I want to share some insights from my experience of becoming a candidate master (almost master, 2081 :( ) on Codeforces.
- Step 1 (for unrated, Newbie or Pupil coders):
As a beginner in coding, you should be solving as many easy and medium problems as you can. Choose any website that you like, be it Hackerrank (Comfortable UI for beginners), Codechef, Codeforces or Spoj (Best selection of questions); sort the problems in decreasing order of the number of submissions, and solve them. Apart from this try to analyse the time complexity of your code as it gives a good idea to think over questions with the help of time constraints.
If you are a Newbie or a Pupil on codeforces, then, you might be struggling in solving the “ad-hoc problems” as they are not based on any particular data structure or algorithm. These problems are designed to make you think and transform your thought process into a working code(sometimes it can be complex with few corner cases). This is where you will develop your problem solving skills, so it is imperative that you go through this phase.
Do not! I repeat, don’t ever jump directly into learning something as complex as Dynamic Programming without making your brain cells work on ad-hoc problems. Why? For the simple reason that you don’t learn to run before you learn to walk. Just think, If you directly study all the data structures and algorithms before solving some ad-hoc problems, then you would try to find these patterns in all the problems and inevitably end up spoiling your normal thinking process to approach a problem.
I would recommend you to do this for at least 100 problems or until you feel confident that in a normal codeforces contest you will be able to solve A and B problems, before moving to the next step. This approach if practiced with dedication is typically enough to reach ratings equivalent and close to Specialist.
- Step 2 (for Specialist and above):
Now comes the point of learning some Data structures and algorithms (No, no DP yet :/). If you see the stats of a general C problem on codeforces, many of them are still ad-hoc or involve easy algorithms like binary search, two pointers, hashing, maths or use of common data structures like map, set, priority queue, stacks, queue. I admit that there are sometimes problems on dynamic programming or graphs and trees, but they are rare, especially these days.
Learn how to use these basic data structures and algorithms in your preferred language and solve as many problems as you can. At this stage, it is advisable to give each and every contest and to upsolve. What is upsolving? Coming back to the contest and solving the easiest problem that you could not solve during the contest. The knowledge of just the simple data structures and algorithms is enough to push you close to expert rating (1500s).
- Step 3: (Rating beyond 1500)
Congrats! if you have reached till here, because here starts your journey to be an exceptional coder. During the natural course of upsolving, you will get occasional questions on DP, Graph, Trees and other fancy data structures and algorithms which marks it as the best time where you should learn about these topics.
A commonly used method to do this is to read the editorial of the problem. Editorials mention the technique to be used. Read about this technique on online resources (topcoder tutorials, codeforces blogs, etc). After that try to solve some easy and direct problems on that topic. Once you have done this, go on to solve the problem to be upsolved. This is also a good time to start giving codechef long challenges. They have questions using amalgamations of various techniques and are very good for learning new data structures and algorithms.
Most importantly, remember that there will be numerous contests during this process when your ratings would fall. Don’t feel demotivated and stop putting in efforts you can increase your ratings anytime if you strive to become a good coder.
Similarly, there would be times when you cross a threshold rating that you were aiming for a long time. Don’t stop giving contests at this point due to the fear of falling again (Even I did so when I reached Candidate Master).
After all, Competitive Programming is a sport, you grow as much as you practice. Different people may grow at different speeds, but those who stop practicing will eventually become stagnant.
Just give your best and soon you will be doing wonders!!