Hunter Johnson for Educative

Posted on Dec 1, 2022 • Originally published at educative.io

What is competitive programming? Competitive programming with C++

#cpp #programming #community #productivity

To many, competitive programming isn't just about typing out code. It's a sport that takes years to master.

In fact, competitive programming isn't just a hobby. Participating in competitions has many benefits: getting a job, improving logical analysis skills, and expanding your creativity.

So, what is competitive programming, and where should you start your learning?

In today's article, we'll provide an introduction to competitive programming and learn about the major topics in competitive programming you'll need to know to enter your first competition. We'll also turn to Yash Kumar, a world finalist at ACM ICPC, for his thoughts and experiences with competitive programming.

We will cover the following:

What is competitive programming?
How does competitive programming work?
Topics in competitive programming
Yash's advice
Wrapping up and resources

What is competitive programming?

Competitive programming is a sport, perhaps even a form of art. It’s an activity that requires creativity and analytical thinking to tackle difficult coding problems.

Competitive programming includes events (usually held over the internet) where participants, called sport programmers, solve specific problems or puzzles.

Judging, usually done by host machines, is usually based on the number of problems solved under a time constraint. The goal is to write source code that solves a given logical or mathematical problem.

These competitions have been around since the 1970s, and interest in the events has grown significantly over the years, including international contests and a worldwide community. These events are recognized by several large companies, like Facebook and Google.

Well-defined problems: In a competition, you will be given a few problems. These problems will be well-defined, i.e., you are given constraints of variables, assumptions, and any other limitations.
Computer programs: You will be writing computer programs and source code that solve the given problem. It’s important to note that these computer programs are simple command-line programs, not fancy GUIs or web applications.
Specified limits: You will be asked to develop a program with a specified time and memory limit. This constraint will force you to problem-solve and develop creative ideas. You will also be constrained to a set of allowed programming languages.

Competitive programmers participate in contests like ACM ICPC, Google CodeJam, Facebook HackerCup, and many more. In these competitions, competitive programmers use their knowledge of algorithms, data structures, logical reasons, and other skills to solve difficult algorithmic problems.

This is especially difficult because competitors are required to develop programs in a limited time frame. The most common programming languages for competitive programming are Java and C++ due to their relative run-time efficiency compared to other languages like Python or JavaScript.

Benefits of competitive programming

When we asked Yash Kumar, a world finalist at ACM ICPC and creator of Educative's course, Competitive Programming in C++, about why he started competing in competitions, he said:

“It started out as just a hobby. There were constant challenges and new topics to learn. Participating in contests always made it an interesting learning experience. It didn’t start as something I was doing to crack software developer interviews, but it did help a lot. It soon became about demonstrating my skill in online and on-site competitions. Obviously, I had no income back then, so prizes were an added bonus.”

The skills needed for competitive programming have long-lasting benefits for your career as a developer. There are numerous benefits to participating in competitive programming, including:

Getting hired

Participating in competitive programming can make you a desirable candidate for companies. When you participate in large competitions like the ACM International Collegiate Programming Contest, you have a good chance of being on the radar of companies like Apple, Facebook, IBM, Google, and more.

Tech companies track competitions and events to find potential employees. Large competitive programming events are extremely prestigious and difficult to succeed in, so if you do well, that is an indicator of your technical talent and abilities.

That’s why many companies have actually sponsored programming competitions.

Teamwork skills

When you participate in these competitions, you will often work in teams, meaning that you learn how to interact with teammates during high-pressure moments. This is an incredibly important skill.

When you are working as a software engineer, you will almost always work with other individuals, meaning that companies care a lot about your communication and team skills. Also, most teams will have a leader.

If you are the leader of the team, this demonstrates management skills, making you even more of a desirable candidate. Companies want to know that you can work effectively and comfortably with your teammates.

Interview prep

When you are trying to get an engineering job, companies will test you for your knowledge of data structures and algorithms. When you participate in competitive programming, you work to develop an advanced understanding of these concepts.

Furthermore, the environment for the coding interview and competitive programming is quite similar. They are both high-pressure environments in which you have to engage in problem-solving.

While many others may not be able to adjust to this environment, your competition experience gives you an advantage.

Makes you faster and more focused

When you train and participate in programming competitions, you become more disciplined, faster, and more efficient. In this environment, you solve problems and code with a tight deadline. This teaches you how to focus on a task and efficiently execute it.

Though competitive programming helps you get a job, Yash wanted to make it clear that you should not start competitive programming solely for the purpose of getting a job:

"This is something I’ve stressed about in the course as well. You can get a job by taking an interview preparation course and practicing a limited set of topics. You don't showcase your competitive programming talent anywhere for a decent job.

This is a sport and should be treated like one. You do it because you enjoy the time you put into it and get something to show for it. Competitive programming will definitely help you with your job interviews, but you don't have to do CP to prepare for those.”

How does competitive programming work?

Prerequisites

Programming languages: Before getting started with competitive programming, you want to have a good knowledge of a programming language and basic data structures. C++ is the most used language in competitive programming due to its speed.

Data Structures and Algorithms: After choosing your languages of choice, you need to review the fundamentals of data structures and algorithms. Understanding data structures and algorithms are the heart of competitive programming, as they are the way to solve the problems you are given.

Applications and Time Complexity: Beyond just knowing the concepts, you need to know what, when, and where to apply them. This means knowing which data structure should be used for a certain problem for the most optimal solution. You'll need to understand the concepts of time and space complexity, like Big O Notation. This is key when being a competitive programmer because much of your placement revolves around how quickly you can solve the problem.

Practice, practice, practice: So, you’ve determined your programming language of choice and learned about data structures and algorithms. Now, you should continue practicing. You want to start practicing on some online platforms before participating in an official contest.

The Competition

If you’re ready to participate in an official competition, here are some to consider:

International Collegiate Programming Contest (ACM ICPC)
TopCoder
The International Olympiad in Informatics (IOI)
The International Conference on Functional Programming (ICFP).

Google also hosts a number of programming contests like Google Code Jam, Google Hash Code, and Google Kickstart. Here's a word of advice from Yash before you get started:

“Competitive programming is a sport, if you don’t enjoy the process, it’s probably not for you. Developers are problem solvers, using existing knowledge to solve an unknown problem. CP makes you a better problem solver than non-CP developers. The same is the reason why many companies will go beyond a typical SD interview into CP to hire better problem solvers, especially at earlier levels.”

So, what do the competitions look like? A majority of the programming problems and challenges you will be given are mathematical or logical in nature, typically involving one of the following categories: combinatorics, number theory, graph theory, geometry, string analysis, and data structures. The process of solving a problem normally involves two steps.

First, constructing an efficient algorithm.
Second, implementing the algorithm in a suitable programming language.

Typically, you’ll be judged automatically by host machines. All the solutions submitted by contestants will be run on the judge against a series of test cases. Most of the time, problems have an all-or-none marking system, meaning that the solution is either accepted or rejected. The faster you complete an accepted solution, the higher the online judges will rank you.

Topics in competitive programming

C++ refresher

C++ is by far the most popular programming language for competitive programmers. It offers a library called STL (Standard Template Library). STL is a collection of C++ template classes that provides common data structures and functions.

C++ is followed by other languages like Java, an Object-Oriented Programming language. Java offers extensive libraries for data structures called Collections. Still, it’s a bit slower than C++, which is a downside.

Another popular language in competition programming is Python because of its user-friendly functionality, as the code is significantly shorter and more concise than other programming languages. The downside to using Python is that it is quite slow compared to C/C++ and Java.

Complexity analysis

Before you dive into data structures and algorithms, it’s important that we cover complexity analysis, which is a way to describe an algorithm’s performance and efficiency as the input grows larger. It’s important that you analyze your algorithm’s runtime complexity to determine whether your solution is going to meet the time limit.

There are three cases to consider:

Best case
Average case
Worst case

When you are participating in a competition, you want to focus on the worst-case analysis. Typically, the inputs will force your solution to its worst-case performance.

Big O notation is an asymptotic analysis that describes how long an algorithm takes to perform. In other words, it’s used to talk about how efficient or complex an algorithm is.

Data structures

A data structure is a container that stores data in a specific layout. This "layout" allows a data structure to be efficient in some operations and inefficient in others.

Understanding data structures is integral to participating in competitive programming, as you will be faced with making decisions on what data structure to utilize to most efficiently solve the problem you are given. If you've taken a computer science course in college, you most likely are familiar with data structures. You should cover:

Arrays
Stacks
Queues
Linked List
Binary Tree
Binary Search Tree
Graphs
Tries
Hash tables
Heap

Looking for a refresher on data structures? Visit our Top Data Structures and Algorithms to know article.

Number Theory

Competitive programming deals with a lot of math, so it's important to review mathematical concepts used by developers. Let's review some of the main topics covered in competitions. These basic fundamentals can make or break your success!

Algebra:

Natural numbers are all positive integers starting from 1 (ex: 1, 2, 3, 4, 5, 6, 7…)
The sum of the first n integers is calculated n(n+1)/2
Factorial is denoted by n!, i.e., n! = 1 * 2 * 3... n
Prime numbers are natural numbers greater than 1 that cannot be made by multiple other whole numbers

Arithmetic Sequence:

Arithmetic sequences are a series of numbers such that the difference between each consecutive number is constant. For example, an arithmetic sequence could be 1,3,5,7.., since the common difference is 2.

The Sum of an arithmetic sequence with n terms is =n[2a + d(n-1)]/2 with n denoting the number of terms, a denoting the first term, and d denoting the common difference.

Geometric Sequence:

Geometric sequences are a series of numbers such that the next term is obtained by multiplying the previous term with a common multiplier. For example, 2, 4, 8, 16, 32. The common multiplier is 2.

The Sum of a geometric sequence with n terms is a(1-r^n)/(1-r) where r is the common multiplier, n is the number of terms, and a is the first term.

Algorithmic paradigms

Algorithmic paradigms are general strategies for solving a problem. There are four popular forms of algorithmic paradigms: brute force, divide & conquer, greedy algorithms, and dynamic programming. Today, you will learn about Brute Force and Dynamic Programming (DP).

Brute force algorithms are exhaustive methods of solving a problem by trial and error. It takes advantage of sheer computing power and tries every single possibility to find a solution. An example of a brute force algorithm is linear search, a method to find a target value by iterating through every single value in a list.

Dynamic Programming is an algorithmic strategy for solving a problem by breaking it down into smaller subproblems by utilizing the fact that the optimal solution to the original problem depends upon the optimal solution to its subproblems.

Graph algorithm

A graph is a non-linear data structure that consists of nodes and edges. These nodes can also be referred to as vertices. Below is a visualization of a graph.

Popular Graph concepts to learn:

Breadth First Search (BFS)
Depth First Search (DFS)
The shortest path from the source to all vertices (Dijkstra)
The shortest path from every vertex to every other vertex (Floyd Warshall)

Yash's advice

"Get yourself around people who enjoy CP. Having a group like this definitely was one of the top reasons why CP never became boring for me. Discussing new problems late at night with your friends after a competition might sound nerdy but having a motivated circle will keep you motivated.

I often see students spending months on CP theory and never participating in a competition (online or onsite), fearing that they don’t know enough to start competing, or fearing the pressure of a timed contest. Writing accurate and fast code is a huge part of CP and this can only be improved by getting into a live contest."

– Yash Kumar

ACM ICPC, World Finalist

Wrapping up and Resources

Now that you have a sense of what competitive programming is and what concepts you'll need to brush up on before competing.

Yash has compiled his years of experience and passion for competitive programming into a one-stop-shop course for beginners. His guide walks you through the process, insider tricks, and all the concepts you'll need to master. Get started with Competitive Programming in C++: The Keys to Success.

Continue reading about C++ on Educative

Start a discussion

What intrigues you about competitive programming? Was this article helpful? Let us know in the comments below!

DEV Community