C++ for Competitive Programming - Tips and Tricks

Why C++ for Competitive Programming? permalink

C++ is by far the language of choice for competitive programming. According to IT shared, around 90% of code submissions in Codeforces are made in C++.

The main benefit of using C++ for competitive programming is speed, efficiency and type safety. Compared to a high level language like Python, C++ is from 10 to 100 times faster.

This is crucial when working on problems with tight time limits.

Let’s say there’s a problem with a constrain of $1 \leq n \leq 450$ and you have an algorithm that solves it with a complexity of $O(n^3)$ . In contest settings, the server is capable of processing up to $10^8$ operations per second.

So this $O(n^3)$ should pass without problem if implemented correctly.

Well, if you try to solve it using the following code in Python, it would surely take more than a second.

n = 450
cnt = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            cnt += 1

print(cnt)

# Results
________________________________________________________
Executed in    5.38 secs    fish           external
   usr time    5.38 secs  287.00 micros    5.38 secs
   sys time    0.00 secs  157.00 micros    0.00 secs

The equivalent code in C++ yields a much faster result.

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n = 450;
  int cnt = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++)
        cnt++;
  cout << cnt << endl;
}
// Results
________________________________________________________
Executed in  164.55 millis    fish           external
   usr time  163.29 millis  284.00 micros  163.00 millis
   sys time    0.00 millis    0.00 micros    0.00 millis

C++ is also slightly faster than Java. However, Java has quite interesting feautures like the BigInteger class, useful when solving problems with numbers greater than the max capacity of a long long in C++.

The main reason why C++ is faster than these two languages is because C++ is a compiled language, which means the C++ source code gets translated directly into machine code by the compiler. Java source code is compiled into bytecode, and then executed by the Java Virtual Machine. Python is interpreted from start to finish, so it makes sense it’s the slowest of the three.

Another reason why C++ is so vastly used is its powerful standard library and macros. Let’s go over these two.

Using C++ for Competitive Programming permalink

Here’s the tipical template you would find in a codeforces submission.

// Made by Daniel Diaz (@Danidiaztech)
#include <bits/stdc++.h>
using namespace std;

int main(){
    // Code
}

Let’s explain this code.

• The #include <bits/stdc++.h> line includes the whole standard library of C++.
• using namespace std; allows us to use all the functions inside the standard library without typing std::function.

Basic Standard Input/Output permalink

In C++, you can take the input with the cin object, and the >> operator.

int n;
cin >> n;

This is going to take a number from the standard input, and store it in the variable n of type int.

Usually you have to read a number multiple times. Let’s see an example of a program that calculates the maximum number present in the standard input.

// Made by Daniel Diaz (@Danidiaztech)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    // Number of times we're gonna take the input
    cin >> n;
    int mx = -1000000;
    for (int i = 0;i < n; i++){
        int a;
        cin >> a;
        mx = max(a, mx);
    }
    cout << mx << endl;
}

In other problems, we have to take the input until the end of the file (there is no more input to take). We can do so with a while loop, and the cin object.

// Made by Daniel Diaz (@Danidiaztech)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int a;
    int mx = -1000000;
    while (cin >> a){
        mx = max(a, mx);
    }
    cout << mx << endl;
}

As you may have already noticed, to send output we use the cout object along with the << operator.

cout << "Text" << endl;

The endl function inserts a new-line and flushes the output stream. This is important in interactive problems.

You can concatenate chains of text and printable objects (like integers, and strings) with the << operator.

int n = 5;
cout << "The special" << " number "<< n <<  endl;

Basic Math Operations permalink

In competitive programming we usually use two types of objects to represent integers, int, and long long.

An int in C++ has 32 bits, that means, you can fit an integer from $-2^{31}$ up to $2^{31} - 1$ . If you go over or under these limits, you’ll have integer overflow and your program is likely to fail.

In some problems, is necessary to use a bigger integer type like long long that can fit numbers of 64-bits.

You can access these numeric limits in the following way.

cout << INT_MIN << endl;
cout << INT_MAX << endl;
cout << LLONG_MIN << endl;
cout << LLONG_MAX << endl;

// Result
-2147483648
2147483647
-9223372036854775808
9223372036854775807

You can perform the basic arithmetic operations like addition, substraction, multiplication and division in the following way.

int a = 4;
int b = 5;
cout << a + b << endl; // Addition
cout << a - b << endl; // Substraction
cout << a * b << endl; // Multiplication
cout << b / a << endl; // Division

Note that in C++ the / operator changes according to the data types we’re working with. If at least one of the numbers involved is a decimal number, then the division will be float division. By default the division between any two integers is integer division.

There’s also the modulus %, increment ++ and decrement -- operations. These last two, add or decrease the variable they are applied to by 1.

int a = 4;
cout << ++a << endl; // Out: 5, a: 5
cout << a++ << endl; // Out: 5, a:6
cout << a % 2 << endl; // 6 % 2 = 0
cout << a % 4 << endl; // 6 % 4 = 2

You can also perform more complicated operations like power, or logarithm by using the cmath library.

However, stay away from them in contests since they can introduce errors in large test cases.

Strings permalink

In C++, you have the string class which is basically a container of characters. These are stored inside double quotes "". A char is a primitive data type used to store a single ASCII character, you store chars inside single quotes ''.

You can access chars inside strings like you would with elements inside a vector (you can also perform push_back() and pop_back()).

Useful methods of the class string are substr and size().

string abc = "abc";
cout << abc[0] << endl; // a
cout << abc.size() << endl; // 3
cout << abc.substr(1, abc.size()); // bc

It is also possible to concatenate strings with the + operator.

string a = "hello";
string b = " world";
cout << a + b << endl;

Converting data types permalink

Sometimes it’s necessary to convert integers to chars or strings, or vice versa.

• String to integer, or long long

int num = stoi(s);
long long big_num = stoll(s);

• Char to integer

int num = ch - '0';

• Integer to string

string s = to_string(num);

• Integer to char

char ch = ('0' + 8);

Basic Data Structures permalink

Let’s go over the basic built-in data structures we use in competitive programming.

1. Array

An array is a contiguous space in memory used to store elements of the same type. You can access the elements of an array with the [] operator, and the index (position) of a specific element.

int arr[5] = {1, 2,3 ,4,5};
cout << arr[1] << endl; // 2

Note how we have to define the type of the elements of the array.

To iterate through an array you access its positions (from 0 to n - 1) with a for loop.

int arr[5] = {1, 2,3 ,4,5};
for (int i =0 ; i < 5; i++){
cout << arr[i] << " ";
}

2. Vectors

Vectors are dynamic arrays or containers that can modify their size in runtime. This time you’ll have to define the type of the vector inside the <T> parameter, and before the name of the vector.

vector<int> my_vector;

We can initialize a vector with a default value, and size.

vector<int> defined_vector(5, 7); // 5 5 5 5 5 5 5

The first parameter is the default value, and the second is the initial size.

You can add values to the end of the vector by using the push_back() method, and remove elements from the end with pop_back().

defined_vector.push_back(12);
defined_vector.push_back(13); // vector: 5 5 5 5 5 5 5 12 13
defined_vector.pop_back(); // vector: 5 5 5 5 5 5 5 12 

With the help of these two methods you can use the vector data structure as a stack.

4. Ordered and unordered maps

An ordered map is a sorted container that contains key-value pairs. The main difference between ordered and unordered maps is the time complexity. The ordered map allows access to the elements in $O(log(n))$ , and the unordered map in $O(1)$ .

However, it’s better to use ordered maps when submitting problems because there could be tricky test cases that produce tons of collisions inside the unordered map, thus increasing the time it takes to access elements.

To create an ordered map you do the following:

map<char, int> mp = {{'R', 2}, {'L' ,1}, {'U', 3}};
map['R']; // 2
map['W']; // 0 -> Creates key and assigns it to 0

As you can see you must define the type of each element of the key-value pairs inside the map.

Because this kind of map has an order you can iterate over it.

for (auto x: mp){
    cout << x.first << " " << x.second << endl;
}

To create an unordered map you can:

unordered_map<int, int> mymap;
mymap[3] = 23;
mymap[1] = 2;

5. Sets A set is a container that stores unique elements of a specific type. In C++ sets, are ordered by default, and the complexity of insertion and retrieval of elements is $O(log(n))$ .

set<int> s;
s.insert(1);
s.insert(15);
s.insert(342);

You can insert elements with the method insert(), and find elements with find() which returns an iterator to the element. If an element is not found, then the function returns an iterator to the end of the set (name_of_set.end()).

cout << *s.find(342) << endl; // 342

Macros permalink

A macro in C++ is a label defined in the source code and replaced by its value (or definition) before compilation.

Think of it as shortcuts we can apply to our code to make things easier when writing.

Some macros that are usually used in competitive programming are:

#define ff first
#define ss first
#define pb push_back

After the definition of the macros you can write the following code without raising errors.

vector<int> v= {1,2,3};
v.pb(4);
v.pb(5);

// With pairs
pair<int, int> p(1,2);
cout << pair.ss << endl; // 2

We can also use macros to define our own functions, for example a for loop similar to Python’s.

#define forn(i, n) for (int i = 0; i < n; i++) // for in range in python
#define fore(i, a, b) for (int i = a; i < b; i++) // for in range in python

Wrapping Up permalink

Now you know the basics of C++ for competitive programming. It’s time to solve problems with this new knowledge.

Practice Problems permalink

• Watermelon
• Way too long words
• Coin Piles
• Odd queries
• Vanya and Fence
• Movie Festival