IUSACO

Allows for traversal of a container with the help of a pointer.

for (vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) {
    cout << *it; //prints the values in the vector using the pointer
}

Alternate way to achieve the same with a for-each loop and auto.

for(auto element : v){
    cout << element; // prints values in vector
}

Addition and deletion at the end in O(1) time and in the middle in O(n) time.

vector<int> v;
for(int i = 1; i <= 10; i++){
    v.push_back(i); // stores 1 to 10 in a dynamic array
}

Vectors can be made static sized by initializing it with a size, vector<int> v(30);. They also support an v.erase() operation. A dynamic array can be sorted (default ascending) by sort(v.begin(), v.end()).

Stacks: LIFO with operations push (add at end), pop (remove at end) and top (show end) all of which are O(1). Declared as stack<int> s.

Queues: FIFO with operations push (add in front), pop (remove at end) and front (show end) in O(1).

Deques: Combination of a stack and a queue supporting insertion and deletion from both front and end. Operations are aptly named as push_back, push_font, pop_back and pop_front.

Priority Queues: Supports insertion of elements and deletion and retrieval of element with highest priority in O(log n) where priority is based on a comparator function (highest element in front). Has push (add at end), pop (remove at end) and top (show end) operations and is declared as priority_queue<int> pq;.

A set is a collection of objects having no duplicates.

Unordered Sets: Work by hashing that is, assigning a unique code to every object allowing for insert, erase and count (set contains element then 1 else 0) in O(1). Traversal is pointless. Declared as unordered_set<int> s.

for(int element : s){
    cout << element << " "; // iterating through a set, arbitrary order
}

Ordered Sets: Insertion, deletion and search needs O(log n) time. Has additional operations begin() (iterator to lowest element), end(), lower_bound() (iterator to least element ≥ some k) and upper_bound().

Multisets: A sorted set allowing multiple copies of same element, whose count operation returns the number of times an element is present in set. Time complexity of this operation is O(log n + f) where log n factor searches for element and f factor iterates through sorted set to get count. Declared as multiset<int> ms.

A map is a set of ordered pairs called key and value where keys must be unique but values can be repeated. Supported operations are addition and removal of key-value pair and retrieval of values for a given key. Unordered maps perform aforementioned methods in O(1) whereas for ordered maps it’s O(log n), sorted in order of key.

Unordered Maps: In map m, m[key] = value operator assigns value to a key and places the pair on the map, m[key] returns value associated with the key, count(key) checks for existence of key in the map and erase(it) removes pair associated with a key or iterator. Declared as unordered_map<int, int> m.

Ordered Maps: Supports additional operations lower_bound and upper_bound which return iterators pointing to lowest entry not less than/ strictly greater than a specified key.

map<int, int> m; // [(3,5); (11,4)]
m[10] = 491; // [(3,5); (10,491); (11,4)]
cout << m.lower_bound(10)->first << " " << m.lower_bound(10)->second << "\n";
// 10 491
cout << m.upper_bound(10)->first << " " << m.upper_bound(10)->second << "\n";
// 11 4
m.erase(11); // [(3,5); (10,491)]

Simulation refers to the act of doing precisely what the problem statement states and nothing else; essentially simulating it.

Brute forcing through all the possible cases in solution space to arrive at the solution. To iterate through all permutations of a list:

do {
    check(v); // process or check the current permutation for validity
} while(next_permutation(v.begin(), v.end()));

C++ has built-in function for sorting in ascending order: std::sort(arr, arr+N) or for a vector sort(v.begin(), v.end()). For sorting in a self-defined order, one must use a custom comparator.

Algorithms that select the most optimal choice at each step, instead of looking at the solution space as a whole. Usually in a greedy algorithm, there is a heuristic or value function that determines which choice is considered most optimal. The choice of the greedy algorithm matters too, for example in a scheduling problem choosing earliest starting next event would be incorrect, instead one should go for earliest ending next event because that would give one more choices for future events.

Greedy won’t work in all scenarios though, for example in the fairly popular coin change problem, if the denominations are {1,3,4} then greedy solution would be {4,1,1} but the correct least amount of coins would be two {3,3}. Similarly it cannot work for the knapsack problem which is solved using Dynamic Programming.

Graphs (N vertices and M edges) are usually given in the format: N M followed by the M edges each showing the connecting vertices. One thing to note is that a graph should be stored globally and statically, for access outside the main method. A graph can be represented in three ways:

int n, m;
vector<int> adj[MAXN];
bool visited[MAXN];

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--; // subtract 1 for vertex since array is zero-indexed
        adj[a].push_back(b);
        adj[b].push_back(a); // omit for directed graph
    }
}

// For a weighted graph:
struct Edge {
    int to, weight;
    Edge(int dest, int w):
    to(dest), weight(w)
    {
    }
}

int n, m;
int adj[MAXN][MAXN];

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a][b] = 1; // or w for weighted graph
        adj[b][a] = 1; // ignore this if directed
    }
}

struct Edge{
    int a, b, w;
    Edge(int start, int end, int weight):
    a(start), b(end), w(weight)
    {
    }
    bool operator<(const Edge & e)
    const{
        return w < e.w; // ascending weight sort
    }
};

int n, m;
vector<Edge> edges;

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, w;
        cin >> a >> b >> w;
        a--; b--;
        edges.push_back(Edge(a, b, w)); // add edge to list
    }
    sort(edges.begin(), edges.end());
}

void bfs(int start){
    const int total_nodes = n;
    memset(dist, -1, sizeof dist); // fill distance array with -1s
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    int seen = 1;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int e: adj[v]){
            if(dist[e] == -1){
                dist[e] = dist[v] + 1;
                 // see: https://observablehq.com/@yurivish/efficient-graph-search
                if(++seen == total_nodes) break;
                q.push(e);
            }
        }
    }
}

void dfs(int node){
    visited[node] = true;
    for(int next : adj[node]){
        if(!visited[next]){
            dfs(next);
        }
    }
}

Its DFS but on a grid and the aim is to find the connected component of all the connected cells with the same number. As opposed to an explicit graph where the edges are given, a grid is an implicit graph where the neighbours are nodes adjacent in the four directions.

When doing floodfill, an N x M array of bools visited is maintained and a global variable for the size of currently visiting component. The search function is called recursively from squares on all four sides of the current one.

int grid[MAXN][MAXM];
int n, m;
bool visited[MAXN][MAXM];
int currentCompSize = 0;

void floodfill(int r, int c, int color){
    if(r < 0 || r >= n || c < 0 || c >= m) return; // outside grid
    if(grid[r][c] != color) return; // wrong color
    if(visited[r][c]) return; // already visited

    visited[r][c] = true; // mark current sq as visited
    currentCompSize++;
    // recursively call floodfill for neighbour sqs
    floodfill(r, c+1, color);
    floodfill(r, c-1, color);
    floodfill(r-1, c, color);
    floodfill(r+1, c, color);
}

int main(){
    /*
     * additional stuff here
     */
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!visited[i][j]){
                currentCompSize = 0;
                floodfill(i, j, grid[i][j]);
            }
        }
    }
}

It supports two operations:

• Add an edge between two nodes
• Check if two nodes are connected

For this, the sets are stored as trees; initially each node is its own set then the sets are combined when an edge is added between two nodes.

int parent[MAXN]; // store root of each set

void initialize(int N){
    for(int i = 0; i < N; i++)
        parent[i] = i;      // initially, root of each set is node itself
}

int find(int x){            // find root of set of x
    if(x == parent[x])
        return x;           // if x is its parent, it is the root
    else
        return find(parent[x]);
}

void union(int a, int b){   // merge sets of a and b
    int c = find(a);        // find a's root
    int d = find(b);        // find b's root
    if (c != d)
        parent[d] = c;      // merge sets by setting parent of d to c
}

The naive recursive implementation of find can be improved from O(nm) by path compression; the idea being reassignment of nodes on recursive calls to find to prevent formation of long chains and the runtime becomes O(n log n).

int find(int x){
    if(x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}

• DAGs (Directed Acyclic graphs) by virtue of not having any cycles allows them to have an ordering of nodes such that for any edge from u to v, u appears before v (topological sorting).
• Bipartite graph is such that each node can only be colored by 2 colors such that no adjacent nodes share the same colour. A graph is bipartite iff there are no cycles of odd length. A modified BFS can be use to check whether a graph is bipartite or not.

To process queries to find the sum of elements between two indices in a list, prefix sum is useful. Using 1-index in the array is beneficial i.e. assigning arr[0] = 0 and hence prefix[0] = 0.

\(prefix[k] = \sum_{i=1}^{k}arr[i] = prefix[k-1] + arr[k]\)

For processing Q queries consisting on an array of N elements, the complexity is O(N+Q).

Prime factorization of a number is computed by this algorithm in \(O(\sqrt{n})\):

i	n	v
2	252	{}
2	126	{2}
2	63	{2,2}
3	21	{2,2,3}
3	7	{2,2,3,3}
7	1	{2,2,3,3,7}

GCD using Euclidean Algorithm in O(log min(a,b)):

int gcd(int a, int b){
    if(!b) return a;
    return gcd(b, a % b);
}

LCM can be computed using GCD by \(\frac{a \times b}{gcd(a,b)}\)

Modular Arithmetic is useful for dealing with overflows by taking remainders:

\[\begin{align*} (a \pm b)\mod m &= (a\mod m \pm b\mod m)\mod m \\ (a \times b)\mod m &= ((a\mod m) \times (b\mod m))\mod m \\ a^{b}\mod m &= (a\mod m)^{b}\mod m \end{align*}\]