Fundamentals of 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.