Competitive Programmer s Handbook

Basics

Key Types

Basic Types

long long - always 64 bits long double - 80 bits

Compare floats with:

if (abs(a - b) < 1e-9) {

Tricks

typedef long long ll

Math

sum(i..n) = n(n+1) / 2

sum(i)

Time Complexity

  • O(2n) means you iterate through each subarray of an array of size n
  • O(n!) means you iterate through all permutations of an array of size n

Data Structures

string s = "abde";
cout << s.substr(1, 2); // substring from index 1 with length 2

Sets

set s;
s.insert(5);
set.erase(5);

bitset<10> s; // bitset with 10 elements

bitset<10> s(string("01100101"));

Maps

// uses a balanced binary tree. Access take O(log n)
map<string, int> m;

// uses hashing. O(1) access
unordered_map<string, int> m;

Using Iterators

reverse(v.begin(), v.end());

for (auto it = s.begin(); it != s.end(); it++) {
        cout << *it << "\n";
}

if (s.find(el) != s.end()); // ...


auto it = s.find(el);
cout << *it << "\n";

Deque

deque<int> d;
d.push_back(5);
d.pop_back();

Priority Queues

priority_queue<int, vector<int>, greater<int>> q;

Brute Force - Complete Search

void search(int k) {
  if (k == n) {
    // process subset
  } else {
    search(k + 1);
    subset.push_back(k);
    search(k + 1);
    subset.pop_back();
  }
}

Backtracking

Begin with an empty solution and extend it step-by-step with possible solutions

  • This is for when you want all possible solutions