Resources

• https://cses.fi/book/index.php → By Antti Laaksonen

• https://cdn.discordapp.com/attachments/773688766543560754/812510600164933649/Steven_Halim_-_Competitive_Programming_3__The_New_Lower_Bound_of_Programming_Contests_2013.pdf → Good book

• C++ cheat sheet:

• Set Theory for Programmers | Skerritt.blog → Good summary of set theory

Tips - C++

1. FASTER input and output

ios::sync_with_stdio(0);
cin.tie(0);

2. Don’t use << endl for line breaks, use "\n" ; it’s faster

3. Don’t do this:

int a = 123456789;
long long b = a*a;
cout << b << "\n"; // -1757895751 
// Code copied from Competitive Programmer's Handbook by Antti Laaksonen

Instead change int a to long long or do:

long long b = (long long)a*a;

4. Write your program faster by using typedef

typedef long long ll // Whenever you use ll in the program, it refers to long long

ll a = 5034059340; // Means long long a = 5034059340;

5. Convert int to string and vice versa

// int to string
#include<string>
int x = 23984;
string yay = to_string(x);

// string to int
string testing = "2342"; // String should be a number
int yay = stoi(testing); // Convert to int

6. Convert a number digit char to int

char x = '8'; // a number digit
int y = x - 48; // The value 8 is now stored in y

Tips - Data Structures (C++)

Source: images are screenshots from the book

Guide to Competitive Programming: Learning and Improving Algorithms Through Contests by Antti Laaksonen

Stacks

Last in, First out: LIFO (like a stack of plates)

Queues

First in, First out FIFO (like an ice cream truck line up)

Iterators

An iterator points to a value in a data structure. For example, if we have a vector, v,

Notice that v.end() points outside the last element in v

Use *v.begin() to print out the value an iterator points (change code v.begin() to an iterator name)

Sets

Intro

There are set and unordered_set that have the same operations. Note that all elements in sets are distinct. So inserting the same element again won’t change the set

*Use #include<iterator> #include<set> or #include<

• set operations are in $O(\log n)$

• unordered_set is based on a hash table, operations are on average $O(1)$ time

Accessing elements in a set

Use the function find(x) NOT set_name[] to access values in a set. Note find(x) returns an iterator that points to the element x .

Maps

A map is a pair: a key and it’s corresponding value (analogy: a key unlocks a unique door, and a door can represent a value)

You can think an array as a key-value pair. The index of the array corresponds to a unique value. You can use

• map ”based an a balanced binary search tree and accessing elements takes $O(\log n)$ time” (section 5.2.2 of Guide to Competitive Programming)

• unordered_map ”uses hashing and accessing elements takes $O(1)$ time on average” (section 5.2.2 of Guide to Competitive Programming)

• Remember to include #include<map> or #include<unordered_map>

Here’s the syntax:

You can also initialize a map like this:

unordered_map<string,int> testing {
  {"testing", 5}, {"yellow", 6}, {"Hello", 2}
  };
// Note uniform initialization is used here
// Uniform initialization: initialize variables using {value} instead of = value

And check if a key exists using:

if (testing.count("somekey")) {
// The key exists
}

To list out keys and values, you can do this:

for (auto x : testing){
	cout << x.first << " " << x.second << "\n";
}
// x.first is the key
// x.second is the corresponding value
// note we use x.first NOT testing.first

Or in C++ 17 onwards, you can use this: (called structure bindings)

for(const auto& [key, value] : testing) {
  cout << key << ": " << value << "\n"; 
}

Tips - Misc.

Arithmetic series

An arithmetic series is when the difference between any 2 consecutive terms is the same. For example, $\{1,2,3,4,5,6,7\}$ and $\{-5, -3, -1, 1, 3, 5, 7 … \}$ are arithmetic series because they have a common difference between terms.

Sum of arithmetic series: $S_n = \frac{n}{2} \cdot (a + a + (n-1)(d))$ or $S_n=\frac{n}{2} \cdot (t_1+t_n)$

$t_n = a + (n-1)(d)$

If you need to find the sum numbers like 1+2+3+4+5…., don’t use a for loop. Apply the formula or alternatively use the formula $\displaystyle\sum_{t=0}^{n}1+2+3+ ... +n = \frac{1}{2}\cdot (n)(n+1)$

// Don't do this:
int sum{}; int n = 100;
for (int i = 0; i < n; ++i){
sum += i;
}
// Do this, it's faster
int sum{}; int n = 100;
sum = n*(n+1)/2

Geometric series

To get the next term, you multiply by the same number each time. A geometric series is when the ratio between two consecutive terms is the same.

Sum of a geometric series: $\displaystyle \frac{a(r^n-1)}{r-1}$

$t_n = ar^{(n-1)}$

Set theory

A set is a collection of objects (objects can be numbers, strings, etc.). For example, $X=\{1,2,3,4,5\}$ is an example of a set. Note sets are unordered and each object is distinct.