Getting started with Competitive Programming

What is Competitive Programming?

For those of you who wish for something challenging and stimulating for your brains, I would say competitive programming is worth the shot. Many of you may have heard this term, but not really sure what it means or how to get started with competitive programming. So let’s start with the basics, Competitive Programming is no less a sport than Chess. It is an intense battle  involving mental ability and  your problem solving skills to solve more problems than all others in as little time as possible. Competitive Programming, just like hard math problems, challenges you to think differently and try to obtain an optimal and efficient solution to a problem.

Are CP and DSA Same?

Many times People get confused with Competitive Programming and DSA. Competitive Programming does require you to have some basic knowledge of DSA, but they are not the same. Rather than on Some particular Data Structure or Algorithm, the main focus of Competitive Programming is on problem solving, many a times a simple array would be enough to solve a problem but it would involve manipulation of that simple array in ways that are not defined directly by any algorithm based on the problem and more often than not, specific to that problem only.

How to get Started with Competitive Programming?

Learning the Basic Syntax: Well firstly in order to do competitive programming, one needs to be fast and efficient in any one of these languages (C++, Python or Java) or at least know the basics of how to code. I would advise to go forward with C++, because it is much faster than python (C++ is Compiled whereas python is interpreted) and easier to code than Java (No need to create classes). Note that learning the basics and being able to code fast and efficiently is enough, there is no need to deeply understand the internal workings of the language or learn concepts like Object Oriented Programming for Competitive Programming. Although It is good to have that knowledge, they are of little use to you in Competitive Programming.

Understanding Platforms and Problems: Now having done that, there are many platforms that host a lot of competitive programming problems, some of them are: Codeforces, Codechef, AtCoder etc. All these problems have a simple format, description of the problem, inputs and constraints and expected output. Other than that all these problems have a space and time limit. We will go forward with each of these topics one at a time. Beginning with Time Complexity, it would be great if you learn about it here before moving ahead. A rule of thumb for Competitive Programming is you can have around 1e7 operations in 1 second. Almost all the problems have a time limit of 1 or 2 seconds, so you can perform around 1e7 operations. Moving on to Space Complexity, more often than not you will not need to worry about space complexity in Competitive Programming, Most of the platforms often provide 256 MB memory limit, enough to store  more than 64e6 32-bit integers, and you would not require more than 1e6 in most cases. Just keep in mind these constraints and you are good to go.

Now There is no straightforward way of explaining about problem description, this is something you need to understand on your own, for that try to go through some of these problems, and figure out what is the crux of the problem, try to break the problem into three components, the outer story (which is mostly irrelevant of the problem and written just for reader’s curiosity), the main aim of the problem, the important information provided in the problem. Having Identified these three parts, you can now start thinking of ways of how you can get a solution to the problem.

What now?

I believe you, by now, have some understanding of the problems in CP and are also able to come up with one or more ways to solve them. Now It’s time for you to learn about some important concepts that are vastly used in Competitive Programming, some of them are: sorting, two pointers, binary search etc. As there are openings in chess, similarly there are some strategies in competitive programming learning which you may be able to solve the problems faster or in less time space/time complexity. Knowing how smart you are, You may have already used or implemented some of these tricks on your own in some problem without actually learning about them.

Contests

I believe it’s time for you to finally register in some contests and try out your problem solving skills. You may wonder, what are these contests? Well, contests are a really good way to test your knowledge and problem solving skills, and also to develop it further. Codeforces is one of the platforms that host CP contests in which you have to solve some problems (mostly 6 or 7) in a fixed time limit (generally two hours) with each problem becoming more and more difficult. These contests are given by thousands of people competing with each other for ratings. Ratings as the name suggests is something similar to ELO as in chess. Now there is a lot involved in understanding how some rating is given to someone, or how it changes with contests etc. Just remember this, your rating increase is directly proportional to you doing better than others in contests.

How to Improve?

Editorials

Learning to read and understand how to solve problems through editorials is a must if you wish to improve yourself, but keep in mind never to jump onto editorials without actually first trying the problem yourself. Once you have tried and are unable to solve problems, it's time to read the editorial for that problem, you may realize that what you were trying to solve, require something completely different that you haven’t even heard of, well that's great, now you know what to study next, or it may happen that you missed an important observation needed to solve the problem, believe me that happens quite often, it’s not something to be upset about, it takes time to be grasp problems under pressure of a 2 hour contest, best way to avoid this is to try to solve the same problem after the contest, and then later on move on to Editorials. Editorials can be hard to understand at first, to make it easy try reading those questions you were able to solve on your own, and you will get the hang of it.

Unless you are one in a million, you won’t really need this, but most of us do. When we give contests our rating increases initially but then we get stuck. Some people get stuck at 1500, some at 1200 others at 1000, it doesn’t matter, what really matters is how to get past it. Well CP is a tough sport, there will be times when you may think no matter how hard you try, you can’t really improve your rating, or even if you improve you fall back to your previous rating again. Believe me this happens with everyone. Now getting past this requires either of these two solutions, solving the same number of questions but faster every time, or solving one extra question. In order to solve the same number of questions faster, you need practice. With a lot of practice, you will eventually increase your thinking speed, and will be able to solve fast. What about those that are already solving fast? You guys need to learn more topics, try upsolving the questions of every contest. If you solve A to C, try upsolving D and E, keep practicing, and you will notice that in most of the contests you will be able to solve D now, you will have learnt new topics because many times D may require something new that you may not have learnt or even heard about before.

Coding Buddy

Another important thing to improve in CP is to have a buddy with you, with whom you can discuss your approach for the questions, with whom you can discuss further questions after the contest ends. This will really help you remain focused and also provide your brain with new ideas or ways to approach the problem differently, which may come in handy in some other future contests. Moreover, there are times when you just want to rant about a contest that went really bad, so having a buddy helps :)

Purpose

Now one may wonder, what is the purpose of doing all this, why should one have a higher rating, or why even bother solving these questions. As I said, competitive programming is a sport, give it a little time, enjoy solving questions, challenge yourself with these tasks and you will find it so much fun, you won’t be able to stop yourself from thinking about some questions that you know you are really close to solving but just can’t get it right. Other than that it serves many other purposes, it improves your problem solving ability, which is a great bonus in today’s world. All around you are problems left to be solved, as the technological advancement increases computing power increases, hence more and more problems that were thought unsolvable can now finally be tested. CP also helps improve your mathematical skills, as it is very closely related to math. Still not enough reason for you to get started with it, well maybe this will convince you, many big companies like google, microsoft, amazon etc. require their employees to have some knowledge about being able to solve these CP problems, there are tests that mainly focus on DSA though but many a times they may ask problems that only those with CP background are able to solve, moreover CP gives you an edge even with understanding DSA problems.

What kind of Problems to Solve?

Well if you have been doing CP for more than around 1-3 months, you won’t have a problem choosing these problems for yourselves, but when beginning, make sure to pick problems that don’t require complex or multiple data structures, focus on topics like arrays, strings or STL. Constructive and Implementation type of questions should be your focus, as they will help you to understand how to write good code effectively. If you ever feel confused which problems to solve, simply go to Codeforces and apply a filter of rating range x+100 to x+400, where x is your current Codeforces Rating. If the problems seem simple, increase the rating, out of every 10 if you are able to solve somewhere between 5 to 8 problems, this rating is perfect for you.

What kind of Topics to learn?

Your Seniors will continuously take sessions on the important topics that you need to learn. Now any topic is fine, once your basics of programming are clear. You won’t really find it difficult to start segment Trees, or Fenwick Trees or even some graph Theory algorithm, if you know how to use arrays, strings, STL and other such programming constructs. Although there may be some specific prerequisites for certain topics, just make sure you know those topics, and you are good to go.

What are all different resources to get started?

Here are some links for youtube videos for those who love to watch, as well as some docs in case you prefer to read :)

Getting Started with C++ by Apna College (Youtube)

Bitwise Operators By Errichito (Youtube)

Edu by ITMO Academy (Docs)

The Ultimate Topic List by YouKnowWho (Docs)

Make sure you don’t get lost in just one topic trying to go in depth, it is often better to be a jack of all trades, you can focus on solving extremely complex problems later on, when you have grasp of more topics, as you may encounter that a certain problem that could be solved using two different ways could have been way easier if you knew the second way as well.

This wiki is written by Aniket Sukhija.