COMPETITIVE PROGRAMMING FOR BEGINNERS
How to start Competitive Programming?
Are you a total beginner to Competitive Programming?
Do you always feel like starting Competitive Programming but are too scared to do so?
Did you find the problems too hard to start with?
In this roadmap, we are going to talk about a key topic - How to start Competitive Programming?
For those who don’t know what is Competitive Programming (CP), it is a mind sport with which you compete with individuals from all over the world.
Note: The target audience for this roadmap are total beginners who find Competitive Programming too hard to start with, in the first place.
How will Competitive Programming benefit you in your Career?
You can very well use your ratings [achieved on various competitive programming platforms] on your resume to show how you outstand amongst your colleagues! (Believe it or not, recruiters do get impressed by seeing your performance on online platforms).
You will learn how to approach a problem with the best of the best possible ways, you will learn how to analytically think and solve a problem and analyze it’s space and time complexity.
Every large MNC or Product-based company prefers to have initial filtering round which consists of Competitive Programming problems.
You will get to learn a programming language end to end.
The adrenaline rush that you will get after seeing the green tick and your name on the leaderboard - there’s nothing compared to that.
Refer to this document to know what all is there in the world for you to learn or follow and how they will help you. Don’t start memorizing the contents of it but rather understand them.
We don’t want you to use your brain as a Hard Disk but as Processor.
Step 1: Learn a well-known programming language
You can do competitive programming in any programming language but it is highly recommended that you choose one of C/C++ or Java. The reason being that the time of execution is a key factor in Competitive Programming and so, choosing a language whose time of execution is fast is surely going to give you a benefit. C/C++ and Java are relatively faster, particularly when compared to languages like Python.
It’s better to use C++ because it’s among the fastest in terms of execution time and it provides a lot of inbuilt functionalities, is most widely used and has support for various data structures through STL (Standard template library), however, Java is also a good choice as it supports BigInteger (the ability to store large numbers without the overflow problems).
If you are a total beginner to programming, it is highly recommended that you learn a programming language. Head to our Programming Beginner Roadmap for the same.
Step 2: Starting with Competitive Programming
Before you jump into the world of competitions it would be better to get familiar with I/O style and the way coding is done on the online platforms, for that we would suggest you to:
Start practising on Hackerrank, it has a great IDE and a wonderful beginners program which will help you in getting started. Hackerrank has a great set of problems whose difficulty increases gradually and hence you will not face a sudden rise or fall of difficulty and it also lets you view the test case on which you code failed which will help you greatly in making test cases as well as learning how to debug the code for the case on which it failed. As a total beginner, it is important that you are able to see the test case which failed so that you can learn how to target such corner cases.
Once you are familiar with Hackerrank it would be good to dive a little bit more into a little harder problems for which you can go for SPOJ. SPOJ is not a competitive programming site but it consists of a lot of variety of questions which will help you in learning the implementation of a lot of new data structures and algorithms. If you will solve the first 20 problems on SPOJ you will cover topics like arrays, strings, sorting, searching. If you will solve the first 50 problems you will cover topics like bit manipulation, recursion, backtracking, Graph. If you will solve the first 100 problems you will have covered advanced topics like Dynamic Programming, Heaps, Hashing, Tries and segment trees.
As mentioned above, try to start with Hackerrank and solve at least first 20 problems to get an idea as to how Competitive Programming works.
After you’re done with Hackerrank’s first 20 problems you should move to SPOJ and try to solve few problems here also.
As a side note, we would like to suggest that while you are solving these problems, you shouldn’t really wait for completing them first. Rather, in parallel, you should start participating right away as soon as you get an idea as to how the I/O works because participating in competitions and competing with others are the best part of Competitive Programming.
Note: For those of you who have a little bit Idea of Data Structure and Algorithms, you may want to practice only those parts of Step 3 and 4 below, which you are not familiar with.
Step 3: Get Familiar with Data Structures
Again, Please keep in mind our motive is not to make you memorize these Data Structures or Algorithms in the next step but to show you how can you implement these in real life problems.
We have also added some questions along with each topic so that you can get hands-on experience as to how to apply which data structure in which problem.
Arrays and Vector: A collection of similar data types is called an Array. Vectors are also like arrays but when combined with STL functions they prove to be far more useful than an array in Competitive Programming. Here are some great resources to understand the basics of Arrays and Vectors in C++. If you are going ahead with Java as the programming language, you can do a quick Google Search to find the equivalent Java resources as well.
Arrays and Vector Tutorials:
Problems on Arrays and Vector:
Basic Maths: Problems from basic mathematics and implementation are fairly common in contests as well as in interviews. Therefore, it is recommended that you should have an idea of the fundamental mathematics concepts.
Questions on Mathematical Programming:
Strings: They are collections of multiple characters and can be referred to as an array of characters. String problems are quite common in various programming contests and in fact string problems are among the favourite problems for tech interviewers.
Problems on Strings:
Stack: Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). Stack follows LIFO.
Queue: A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).
Map: Map is by far one of the most useful Data Structures. It can be used to find, iterate, add, delete numbers, and is also one of the most widely used Data Structures.
Step 4: Get Familiar with Algorithms
Algorithms are logics that are implemented on various Data Structures to achieve the desired output.
Time/Space Complexity: Every Algorithm has a Time and Space complexity which refers to the maximum amount of time an Algorithm will take and the maximum amount of memory an algorithm will require. While doing Competitive Programming these two will play a key role in determining the verdict of your solution.
Always try to think of the most optimal solution, that is, one which runs with least time complexity and occupies minimum space.
Sorting: You must have heard of a number of sorting techniques to sort but while doing Competitive Programming most of those techniques prove to be time-consuming hence the STL library comes to rescue, it offers a function sort() which sorts the array in the most optimal way.
Types of Algorithms:
Greedy: A solution in which we move step by step towards our final goal if referred to as greedy algorithm.
Divide and Conquer: As the name suggests, in this we try to make the problem easier by dividing it into a number of subproblems and then solving them one at a time and then combining them all together in the end to give a final answer.
Recursion and backtracking: Recursion in the type of algorithm in which a function calls itself again and again to achieve the final output. It makes use of stack data structure. Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that “works”. It makes use of recursion.
Dynamic Programming: In DP we break a problem into a number of problems and then conquer them one by one and store the outcome of the previous subproblem to compute the output of the next one.
https://www.spoj.com/problems/PPATH/ (Breadth-first Search)
https://www.spoj.com/problems/ONEZERO/ (Breadth-first Search)
https://www.spoj.com/problems/PT07Z/ (Depth-first Search)
https://www.spoj.com/problems/BUGLIFE/ (Depth-first Search)
https://www.spoj.com/problems/SHPATH/ (Shortest path)
https://www.spoj.com/problems/TRAFFICN/ (Shortest path)
https://www.spoj.com/problems/SAMER08A/ (Shortest path)
https://www.codechef.com/problems/DIGJUMP (Shortest path)
https://www.codechef.com/AMR14ROS/problems/AMR14B (Shortest path)
https://www.codechef.com/problems/SPSHORT (Shortest path)
For more information on Algorithms refer to this link: https://www.geeksforgeeks.org/lmns-algorithms-gq/
Step 5: Starting with actual online competitions
Once you are familiar with time complexities, I/O operations of online IDE’s and penalties you can start with actual competitions, for which the following sites provide the best environment for competing with others:
Codechef: Codechef offers three monthly contests in which you can participate and test your skills:
Codechef Long: This is a 10-day long contest and is one of the best contest to start Competitive Programming with as it does not have any wrong answer penalty and gives you a lot of time to think and implement your solution for a particular problem.
Cook-Off: This is a much shorter contest that lasts for 2.5 hours and features 5 problems of varying difficulty, this contest will teach you how to think and implement a solution within a given time constraint,
Lunchtime: This is a 3-hour contest meant for school students. A Lunchtime usually features 4 problems. If you think that the problems in this one are gonna be easy, you are in for big surprise.
Codeforces: Codeforces segregates users into three categories: Div 1, Div 2, Div 3.
Start by solving Div 3 problems at first. Codeforces offers multiple contests in a month and you can even try to start a virtual contest if you like. Don’t get demotivated if you find it difficult to solve more than 2,3 problems or even a single problem during a contest when the contest ends look at the tutorials for the problem that you couldn’t solve and then upsolve it.
Codeforces is also good for beginners as it also helps you in looking at the test cases for which your solution which failed which again, in turn, helps you in debugging as well as learning to make your own test cases for further future problems.
Upsolving is the key aspect of improving yourself, also look at the codes of other programmers as it will help you in improving your own coding style.
As a beginner, you should never care about rating because that is your biggest barrier in trying harder and trying problems out of your comfort zone during a competition. Even if your rating is going down, it doesn't mean you aren't improving; rating is relative to others and isn't a sole grader of what you can do.
Solve as many as possible, but don’t get discouraged if you can’t solve a problem after the contest ends, watch the tutorial and also read the code of other participants to learn the coding style and pattern of others.
Step 6: Practice Practice Practice
People say that practice makes man perfect but in the world of Competitive Programming, no one has ever achieved that mark yet no matter how much you practice you will always miss something but that’s the glorious part of Competitive Programming that you never get done with it.
Don’t lose hope and keep trying and submitting until you get that green tick, because trust me when I say this seeing that green tick is one of the best feelings in this world.
Also read about the world championships that are organized by various prestigious organizations like ACM, Google, Facebook, Vk cup, SnackDown and one of the best ways to secure a job interview with companies like these is Competitive Programming and performing well in the competitions organized by them. But first things first, get up from that couch and start enjoying the sport.
The above roadmap may seem quite challenging to you. However, it is meant to be followed over a period of 3 - 6 months, depending on your speed. We would like to suggest that rather than just following the roadmap, you should try and develop habits that help you improve your Competitive Programming skills. For instance, a simple habit could be - ‘I will solve 3 problems from SPOJ every day’. If you follow this habit, in just 1 month, you’d have solved 90 problems on SPOJ which certainly is a great achievement!