Competitive Programming - An Introduction

Competitive Programming is an art form. It is creative problem solving at its finest, a combination of hard analytical thinking and creativity. Competitive programmers use their knowledge of algorithms and data structures and logical reasoning skills to solve challenging algorithmic problems in a limited time frame.

Java and C++ are extremely popular due to their relative run-time efficiency compared to a language like Python. C++ is my preferred competitive programming language as I love its Standard Template Library (STL) which allows for quick write ups of solutions. Without further ado, lets get right into it.

How to Get Started

Learn C++

I know most people might not want to hear this, but as I mentioned already, Python will be hard to succeed with in competitions. C++ as a language for Competitive Programming is fairly easy to pick up, but like any languages understanding the nuances takes a little bit more time. Here are a couple of resources I found helpful:

Ben Qi’s Github Repository

Book With Problem Set

Principles of Algorithmic Solving

I've also uploaded some youtube videos on the topic

Learn Algorithm Analysis

Algorithm Analysis a llows you to look at the solution you came up with and see whether or not it will run in time for a contest or if it will exceed the time limit imposed by the online judge. Time Complexity analysis as the name suggests, quantifies the amount of time that an algorithm takes to run, it is where the famous O(n) notation comes from. This is called big O notation and yields the worst-case scenario run-time, that is the longest it would take for the algorithm to run. O(n) then means that if there are n elements to perform an operation on, the algorithm would run in time proportional to the n elements. Similarly O(n^2) is proportional to n^2 and O(log n) is proportional to log(n). There are other types of Time Complexity Analysis that are also handy. Here’s a resource to read up on Algorithm Analysis:

Big O Analysis

Learn how to Brute Force Problems

At the start of one’s competitive programming journey you more often than not encounter problems that can be brute forced with simple algorithms and do not require optimization to solve. In this case, you can usually just code out the solution step by step rather than applying specific algorithms. To get good at brute forcing problems, all you really have to do is practice. I would advise practicing rating 1000 problems on codeforces.com. Codeforces is a wonderful site to practice your competitive programming skills on.

Learn Greedy Algorithms

Greedy algorithms make the locally optimal choice at each stage of the algorithm in the hope of finding the global optimum. These are usually more efficient than Brute Force solutions as long as you can come up with a greedy solution. They are not suited to every type of problem and may end up being inefficient if you apply them in places they shouldn’t be used. Here is some great information on Greedy Algorithms:

Brilliant’s Greedy Algorithms Page

Learn Dynamic Programming

Dynamic Programming is an optimization on normal recursion. Essentially it involves solving subproblems, saving those solutions, so that you don’t have to resolve them later on as you would with normal recursion. This greatly reduces time complexity and is helpful on recursive type problems. Again the best way to get good at this is to solve multiple dynamic programming problems.

Educational DP ContestGeeks for Geeks DP

Learn Graph Algorithms

Once you move to the upper echelons of programming competitions you will find a multitude of Graph Algorithm problems. These will include things like finding the shortest path in between two nodes on a graph. In order to succeed at these types of problems, there are quite a few algorithms you need to master.

Depth First Search (DFS)

Breadth First Search (BFS)

Dijkstra’s Algorithm (Used to find shortest path)

Bellman-Ford (Used to find shortest path)

Floyd-Warshall (Used to find shortest path)

Kruskal’s Algorithm (Used to find minimum spanning tree)

Prim’s Algorithm (Used to find minimum spanning tree)

Mastering DFS and BFS first will yield great results as you progress in the world of competitive programming. Now that you know what algorithms and techniques you need to learn, you are ready to find out what competitions you can use to practice your skills.

Major Competitions / Online Judges

United States of America Computing Olympiad(USACO)

The USACO is a competitive programming contest held every year in January, February, March, and December. It is divided up into four divisions, Bronze, Silver, Gold, and Platinum. Each division gets progressively harder, Platinum being the hardest. They also have a training page which is a great place to practice and learn Competitive Programming.

Codeforces

Codeforces is a platform on which a lot of programming contests are held. The problems are usually of a very high quality and they have a large database of past problems covering a wide variety of topics you can use to practice your skills. Codeforces works on a rating system and if you are just starting out I would recommend solving 1000-1200 rating problems.

Atcoder

Atcoder is a wonderful programming contest especially for beginners. They host beginner contests often and they are a great way for newcomers to get into the world of competitive programming and learn how to succeed. Like Codeforces, Atcoder has a large collection of problems for you to work on and improve your skills with.

Benefits

Ok cool, but I’m never going to have to implement Dijkstra’s algorithm on the job right? I’ll just use a built in function or use a library. While these are valid points, the objective of Competitive programming is not to have you implement all these fancy algorithms and data structures from scratch. Rather, it is to develop problem solving skills. Solving a lot of Competitive Programming questions helps you improve your problem solving skills. This is why many companies have you solve Competitive Programming like questions during an interview, not to see whether or not you can implement Dijkstra’s algorithm on the job, but to see if you can problem solve on the fly and take things in your stride.

Now get out there and start programming!