What is competitive programming? Competitive programming with C++
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:
Competitive programming can be a great way to build out your programming skills, get on any major company’s radar, and earn a little extra cash along the way. In this course, you will learn to prepare for competitive programming contests like ACM ICPC, Google CodeJam, Facebook HackerCup, and many more. Each topic is broken down with a healthy mix of theory, code samples, step-by-step solved sample problems, illustrations, useful practice problems, and tips and tricks for faster implementation. You will need some solid C++ foundations coming into this course, but by the end it, you will be confident enough in your C++ skills to take home the win.
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, new topics to learn, and 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 onsite competitions. Obviously, I had no income back then so prizes were an added bonus.”
The skills needed for competitive programming have long-lasting benefits to 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.
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 placing 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 involved 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.
Continue the learning.#
Educative’s Competitive Programming course covers theory, code samples, step-by-step solved sample problems, illustrations, useful practice problems, and tips and tricks for faster implementation! All from your browser with no extra downloads.
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 participate 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…)
-
Sum of the first n integers is calculated
-
Factorial is denoted by , i.e.
-
Prime numbers are natural numbers greater than 1 that can not 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.
Sum of an arithmetic sequence with terms is with denoting the number of terms, denoting the first term, and denoting the common difference.
Geometric Sequence:
Geometric sequences are a series of numbers such that the next term is obtained by multiply the previous term with a common multiplier. For example, 2, 4, 8, 16, 32. The common multiplier is 2.
Sum of a geometric sequence with terms is where is the common multiplier, is the number of terms, and 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. For 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)
-
Shortest path from source to all vertices (Dijkstra)
-
Shortest path from every vertex to every other vertex (Floyd Warshall)
How to prepare yourself for Competitive Programming#
How you prepare differs on which competition you’re participating in. It’s important to note that these competitions can last from two to five hours. There are usually around five questions for shorter contests and around twelve questions for a longer contest. When preparing for these competitions, it is wise to know the time constraints of a contest before practicing so you can pace yourself according to the specific competition.
For your preparation, here’s what you can expect from the varying levels of problems you’ll face. The first few problems generally include logic, basic math, simple data structures, and algorithm problems. As you progress to medium-level problems, you will need to understand the theory and application of complex data structures like graphs, stacks, trees, and more. The most difficult questions are generally a combination of multiple concepts or another more complex topic, such as Dynamic Programming.
After you participate in a few competitions, that does not mean you should let your foot off the gas. Upsolving is a very prevalent practice among competitive programmers. It is the act of using the last competition as preparation for the next. The idea is that when you participate in a contest and solve five out of the seven available problems, you should always solve the next couple of questions after the contest. You can do this by looking at the tutorials, studying other participants’ codes, or whatever it takes to solve these problems.
Seeing each problem as a chance to learn something new leads to better prepare for future contests. Discover what you didn’t know during the competition in order to solve the problem. This is the best thing you can do to improve your contest skills!
11 things to keep in mind for Competitive Coding#
Here are even more helpful competitive programming tips and tricks to help as you start exploring the community:
1. C++ may be the best language for competitive programming but don’t completely disregard the importance of learning languages like Python and Java.
2. Don’t get bogged down by a single question. If you’re spending too much time on a question, you’ll likely have the option to skip it. If you skip a question, keep a tab of it in your mind so that you can revisit it later.
3. Don’t waste valuable time on over-optimization. If your solution is accepted, move on to the next question. Worry about optimizing the solution during your designated practice time. Learn how to optimize your code by reducing time complexity, avoiding unnecessary operations, and using appropriate data structures.
4. Preparing at the last moment means you’ll often need to catch up to expectations. Give yourself enough time to review algorithms, sample problems, and gauge your strengths and weaknesses.
5. Before attempting to type in your answers, it’s vital that you develop the logic behind the problem. After you understand the underlying logic, you can begin to code. This will save you valuable time from having to redo any code during the competition.
6. While prepping for competitions, challenge yourself to learn a new concept daily or strive to solve at least one problem per day. A constant practice routine is key to competition readiness.
7. Don’t compare yourself to others just because it’s a competition. Though it’s fun to compete, don’t get caught up in comparing how fast you’re learning to others. Even though it may be a little slower, everybody learns at their own pace! Simply put, competitive programming is a marathon, not a sprint.
8. Keep track of your mistakes and learn from them. Analyze your mistakes so you can pinpoint where you went wrong.
9. Read other people’s code to learn new techniques and approaches to solving competitive programming problems. You can find a lot of useful code on online platforms and in discussion forums.
10. Join these online coding communities and participate in their discussions and projects with other programmers. Collaborating with others is often the easiest way to learn new concepts and skills.
11. If you’re thinking of how to start competitive programming, check out this collection of Google’s upcoming competitions.
For specific tips and tricks on how to solve competitive programming problems in C++, check out this Answer from Educative Answers!
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 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++#
Free Resources
