Competitive Programming and How to Get Involved in Various Contests

Written by Hugo Dominguez

In this article, you will be introduced to the world of competitive programming, the contests you can participate in, how to improve and what algorithms you should learn.

We will start with a brief introduction to competitive programming, followed by some information about Olympiads and contests you can participate in. We will also list some algorithms and data structures, when it is best to learn them and some resources to practice them.

What is Competitive Programming?

Before we start discussing competitive programming, we need to know what it actually is.

Competitive programming is usually defined as being a mind sport where participants are given some tasks that need to be solved in a specific amount of time.

This usually involves a set of problems which are very similar to that of Mathematics Olympiads’, with the difference that these are expected to be solved using a computer, which takes advantage of its huge computational power.

However, the fact that we are using a computer does not mean that our algorithm can use unlimited resources, as, most of the times, the problems have a limit as to how much time and memory our algorithm should use. The usual constraints are 1 second to execute the code and 256 Mb to use in variables and function definitions.

Practice Problems & Contests

When starting out in competitive programming, you will want to solve lots of problems. A great way to do this is solving practice problems and participating in contests.

PLATFORMS

There are some platforms that have practice problems and organize weekly contests for you to participate in. The most useful ones are HackerRank, Codeforces and LeetCode.

HackerRank

HackerRank is a great platform for beginners, as it has many problems that focus on the mathematical and brute-force aspect of competitive programming, which, most of the time, does not require advanced knowledge in algorithms and data structures. However, HackerRank does not usually host contests, which is why I would advise you to move on to Codeforces once you have a solid foundation of basic programming concepts.

Codeforces

Codeforces is, in my opinion, the best competitive programming platform out there.

With over 10 years of practice problems organized by topics and difficulty, and 2 or 3 weekly contests, it is simply the best resource to get started solving more advanced problems.

In addition to this, once you participate in your first contest, you will receive some rating points, which indicate your level in competitive programming, and can be lost or gained by participating in other contests, which adds some sense of progression to your competitive programming journey.

The fastest way to get better at competitive programming is to participate in as many contests as possible and look at the tutorials of the problems you have not solved after the contest.

LeetCode

LeetCode is the platform that I have used the least. However, it has proven to have some useful problems to solve after learning an algorithm or data structure, as they focus solely on the implementation rather than it being a problem in which you have to apply said algorithm or data structure.

Of course, LeetCode has other types of problems and hosts weekly contests, but I would advise you to just practice in Codeforces.

CONTESTS AND OLYMPIADS

Once you are confident of your competitive programming skills, you will want to participate in some real-life contest or Olympiad. Usually, you will want to attend Informatics Olympiads.

These contests are just like those in Codeforces but you have to attend a physical place. These Olympiads usually qualify you to go to other Olympiads. For example, in Spain there are Regional and National Olympiads.

The winners of the Regional Olympiads go to the National Olympiad, and the winners of this last Olympiad usually go to the International Olympiad in Informatics (IOI).

Algorithms & Data Structures

Once you have spent some time solving some easy problems, you might want to attempt harder ones. However, you might stumble upon problems that require you to know some basic algorithms and data structures to solve them. There are lots of algorithms and data structures, but the most important ones when you are starting out in competitive programming are:

BINARY SEARCH

Binary search is arguably the most useful algorithm in competitive programming.

At its core, binary search is an algorithm that allows you to perform a fast search in an ordered array. Where a standard complete search would have to iterate over all the elements in an array (in O(n) time), binary search makes use of a divide and conquer approach and narrows the search down to just a few elements (in O(logn) time).

Binary search should be the first essential algorithm that any competitive programmer learns.

GREEDY ALGORITHMS

A greedy algorithm is an algorithm that always chooses the most optimal solution in a small subset of the problem, hoping that it will result in the most optimal solution overall.

This is not exactly an algorithm that you can apply in certain cases, but rather a programming technique that you should consider when coming up with solutions to problems.

DYNAMIC PROGRAMMING

Just like greedy algorithms, dynamic programming is not exactly an algorithm or data structure, but rather a programming technique. Oftentimes, when we write an algorithm, we recalculate certain values repeatedly.

However, this is not always necessary, as we can store them and use them later. For example, if we want to calculate the Fibonacci sequence, we can store all the values that we use in an array and reuse them in successive calculations.

GRAPH THEORY

Once you have mastered some basic algorithms, you should consider learning graph theory. Graph theory is an essential topic in computer science, as it allows us to capture real life problems into a problem that can be solved by computers.

At its core, a graph is a group of vertices connected by edges (see Fig. 1). A common example of a graph is a social network, where vertices represent users and edges between two vertices signify that these users are friends.

There are two main ways to represent a graph in our code: adjacency lists and adjacency matrices.

Most of the time, adjacency lists are much more efficient than adjacency matrices. When using adjacency lists, graphs are represented by a vector (see Fig. 2), and, in each index of the vector, there is another vector containing the indices of the neighboring vertices (those connected by an edge).

DFS & BFS

Most graph problems will require you to traverse the graph in some way. There are two main algorithms that can be used for this purpose:

• Depth First Search (DFS): This is the simplest and most useful graph algorithm. It uses a recursive approach to visit all the edges of a graph, starting at the desired vertex and traversing all the possible paths.

• Breadth First Search (BFS): This algorithm is also extremely popular in graph theory, although most of the time, it is better to use DFS, as it is easier to implement. However, there are certain problems in which BFS are required. For example, if we want to calculate the shortest distance from one vertex to all others in an unweighted graph, we will need to use a BFS. Unlike DFS, BFS visits the graph in layers, first visiting the neighbors of the starting vertex, and then moving to the neighbors of the neighbors until all the vertices have been visited.

Competitive Programming Resources

Before wrapping up this guide, I will provide you with some resources that helped me during my competitive programming journey. These resources include videos, websites, books and much more.

COMPETITIVE PROGRAMMER’S HANDBOOK

This book should be in every competitive programmer’s bookshelf. This guide is divided into three sections: basic techniques, graph algorithms and advanced topics.

I would advise you to read the first section of the book and then occasionally look at the graph algorithms and advanced topics sections when you try to learn them. This book is open-source.

CP-ALGORITHMS

This website covers most algorithms and data structures you will need as a beginner or intermediate competitive programmer. Each concept is explained in a very detailed way and has some snippets of code and diagrams that really help you when learning a new algorithm.

YOUTUBE CHANNELS

In my competitive programming journey, I have stumbled upon some YouTube channels that have helped me understand some important computer science concepts. The most useful ones have been WilliamFiset, Errichto and Reducible.

BONUS: LEAGUES OF CODE

Leagues of Code is an online program organized by Harbour.Space that offers students weekly 2-hours-long competitive programming lectures.

I have been enrolled in this program for over 6 months now and I highly recommend it to anyone interested in competitive programming. You can find more information about Leagues of Code here.

Wrap Up

Now that you have a general idea on the topic of competitive programming, I advise you to go and practice some problems on HackerRank, or if you think you can solve harder problems, try solving some Codeforces problems!