Competitive Programming: Algorithms and Data Structure

In this blog, I will cover all the Important and most efficient algorithms, data structures and basics of mathematical concepts used in competitive programming, that will help you to become an expert Competitive Programmer. Here I have made three categories:

  1. Basic Mathematics
  2. Data Structures (Beginner to Expert)
  3. Algorithms.

This blog is the continuation of How to start with Competetive Programming

In each part, I will introduce you with important concepts used in competitive programming (will not go in detail) and will provide a good reference to read these topics in detail.

Basic Mathematics for Competitive Programming

If you want to be a serious competitive programmer. You should have knowledge of some Mathematical concepts and good command on number theory.

Number theory
In number theory, there are many Concepts. Let me introduce you with all these one by one, and that would save a lot of time and efforts while programming in the contests.

1. Modular arithmetic When one number is divided by another, the modulo operation finds the remainder. It is denoted by the % symbol.

Example Assume that you have two numbers 9 and 2. 9%2 is 1 because when 9 is divided by 2, the remainder is 1. More details visit this: Modular arithmetic

2. Modular exponentiation Exponentiation is a mathematical operation that is expressed as (x^n) and computed as x^n = x*x*…*x (n times). But Modular exponentiation In this operation, given three numbers x, y, and p, is competed as compute (x^y) % p.

Example:
Input: x = 2, y = 3, p = 5
Output: 3
Explanation: 2^3 % 5 = 8 % 5 = 3.
More details visit this: Modular exponentiation

3. Greatest Common Divisor (GCD)
The GCD of two or more numbers is the largest positive number that divides all the numbers that are considered.

Example:
The GCD of 20 and 12 is 4 because it is the largest positive number that can divide both 20 and 12.
More details visit this: GCD

4. Euclidean algorithm
The idea behind this algorithm is GCD(A, B)=GCD(B, A%B). It will recurse until A%B=0.

5. Extended Euclidean algorithm
This algorithm is an extended form of Euclid’s algorithm. GCD(A, B) has a special property so that it can always be represented in the form of an equation i.e. Ax+By=GCD(A, B).

The coefficients (x and y) of this equation will be used to find the modular multiplicative inverse. The coefficients can be zero, positive or negative in value. This algorithm takes two inputs as A and B and returns GCD(A, B) and coefficients of the above equation as output.

Example If A=30 and B=20,
then 30∗(1)+20∗(−1)=10 where 10 is the GCD of 20 and 30.
More details visit this: Extended Euclidean algorithm

6. Modular multiplicative inverse
What is a multiplicative inverse? If A.B=1, you are required to find B such that it satisfies the equation. The solution is simple. The value of B is 1/A. Here, B is the multiplicative inverse of A.

What is modular multiplicative inverse? If you have two numbers A and M, you are required to find B such it that satisfies the following equation: (A.B)%M=1 Here B is the modular multiplicative inverse of A under modulo M.

More details visit this: Modular multiplicative inverse

7. Sieve of Eratosthenes
Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number. The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million.

Example:
Input : n = 20
Output: 2 3 5 7 11 13 17 19

More details visit this: Sieve of Eratosthenes

8. Euler’s Totient Function
Euler’s Totient function fun(n) for an input n is a count of numbers in {1, 2, 3, …, n} that are relatively prime to n, i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1.

Example:
fun(6) = 2
gcd(1, 6) is 1 and gcd(5, 6) is 1.
More details visit this: Euler’s Totient Function

9. Convex Hull
Given a set of points in the plane. the convex hull of the set is the smallest convex polygon that contains all the points of it.

 

More details visit this: Convex Hull

Data Structures

Which data structure you will use, that depends on the problem you are trying to solve. If a problem is mapped to the most efficient data-structure which captures the essence of that problem, then it leads to an elegant solution to the problem.

The “right” choice of data-structure would not only depend on the representation of the inputs but the query it is supposed to be optimal for. E.g if asked to find a number among the list of number efficiently, then BST(Binary Search Tree) is a choice which would effectively represent the input data for the set of all point search queries.

If the query was for a range of numbers, and not just a single number, then BST is no longer the optimal choice but the data-structure to choose is maybe B+ Tree.

Here I will categorize the all-important data structures for different – different competitive programming skill level.

Beginner:
1. Linked List
2. Stack
3. Queue
4. Binary Search Tree

Intermediate:
1. Heap
2. Priority Queue
3. Huffman Tree
4. Union-Find
5. Trie
6. Hash Table
7. TreeMap

Proficient :
1. Segment Tree
2. Binary Indexed Tree
3. Suffix Array
4. Sparse Table
5. Lowest Common Ancestor
6. Range Tree

Expert:
1. Suffix Automaton
2. Suffix Tree
3. Heavy Light Decomposition
4. Treap
5. Aho-Corasick Algorithm
6. K Dimensional Tree
7. Link-Cut Tree
8. Splay Tree
9. Palindromic Tree
10. Ropes Data Structure
11. Dancing Links
12. Radix tree aka Prefix tree
13. Dynamic Suffix Array

I have seen all of the listed data structures being used in various programming contests.

Many of them are given in language libraries. But it is very important to understand their dynamics. Otherwise, understanding related higher-level structures will be difficult (if possible).

One may find some higher level data structures easier than lowers (happened to me).

Especially for c++ user

Those programmers use c++ language for their competitive programming they can use some of data structures in STL.

1. Vector
2. List
3. Deque
4. Queue
5. Priority_queue
6. Stack
7. Set
8. Multiset
9. Map
10. Multimap

Algorithms

To be a good competitive programmer you must have a good understanding of the algorithms and the way your code works. The best algorithms are the ones which are small (fewer lines of code) and efficient.

You can develop your mind in building great algorithms by reading the code and practicing writing code.

Here I will introduce you with some of the standard algorithms that we use in competitive programming.

Searching algorithms

  1. Linear Search.
  2. Binary Search.
  3. Jump Search.
  4. Interpolation Search.
  5. Exponential Search.
  6. Ternary Search.

Sorting algorithms

  1. Selection Sort
  2. Bubble Sort
  3. Insertion Sort
  4. Merge Sort
  5. Heap Sort
  6. QuickSort
  7. Radix Sort
  8. Counting Sort
  9. Bucket Sort
  10. ShellSort
  11. Comb Sort
  12. Pigeonhole Sort
  13. Cycle Sort.

Greedy Algorithms
A greedy algorithm is an algorithm that always makes a choice that seems best “right now”, without considering the future implications of this choice.

Greedy Algorithm as the name itself implies is an algorithm that is always greedy in taking decisions at each step of process, i.e. it chooses the best solution (either maximum or minimum / known as local optimum in technical terms) at each step of process assuming that you end up with the best solution (known as global optimum in technical terms) for the whole problem in the end.

Here are some algorithms where the Greedy approach is used:

  1. Activity Selection Problem
  2. Kruskal’s Minimum Spanning Tree Algorithm
  3. Huffman Coding
  4. Efficient Huffman Coding for Sorted Input
  5. Prim’s Minimum Spanning Tree Algorithm
  6. Prim’s MST for Adjacency List Representation
  7. Dijkstra’s Shortest Path Algorithm
  8. Dijkstra’s Algorithm for Adjacency List Representation

Pattern Searching Algorithms
In Pattern searching algorithm we search the pattern that repeats one or more time in the sequence or string. Here I will introduce you with some efficient pattern searching algorithms that find a pattern in a particular sequence or string and finds the number occurrences of a pattern in that sequence or string in optimal time.

  1. Naive Pattern Searching
  2. KMP Algorithm
  3. Rabin-Karp Algorithm
  4. A Naive Pattern Searching Question
  5. Suffix Array
  6. Z algorithm (Linear time pattern searching Algorithm)
  7. Pattern Searching using a Trie of all Suffixes

Graph Algorithms
Some of the most famous graph algorithms are given below:

Introduction DFS and BFS:

  1. Graph and its representations
  2. Breadth First Traversal for a Graph
  3. Depth First Traversal for a Graph
  4. Applications of Depth First Search
  5. Detect Cycle in a Directed Graph
  6. Detect Cycle in an Undirected Graph
  7. Detect cycle in an undirected graph
  8. Longest Path in a Directed Acyclic Graph
  9. Topological Sorting
  10. Check whether a given graph is Bipartite or not
  11. Snake and Ladder Problem
  12. Biconnected Components
  13. Check if a given graph is tree or not

Minimum Spanning Tree:

  1. Prim’s Minimum Spanning Tree (MST))
  2. Applications of Minimum Spanning Tree Problem
  3. Prim’s MST for Adjacency List Representation
  4. Kruskal’s Minimum Spanning Tree Algorithm
  5. Boruvka’s algorithm for Minimum Spanning Tree

Shortest Paths:

  1. Dijkstra’s shortest path algorithm
  2. Dijkstra’s Algorithm for Adjacency List Representation
  3. Bellman-Ford Algorithm
  4. Floyd Warshall Algorithm
  5. Johnson’s algorithm for All-pairs shortest paths
  6. Shortest Path in Directed Acyclic Graph
  7. Some interesting shortest path questions
  8. Shortest path with exactly k edges in a directed and weighted graph

Connectivity:

  1. Find if there is a path between two vertices in a directed graph
  2. Connectivity in a directed graph
  3. Articulation Points (or Cut Vertices) in a Graph
  4. Biconnected graph
  5. Bridges in a graph
  6. Strongly Connected Components
  7. Biconnected Components

Maximum Flow:

  1. Ford-Fulkerson Algorithm for Maximum Flow Problem
  2. Find the maximum number of edge-disjoint paths between two vertices
  3. Maximum Bipartite Matching

Dynamic Programming
In Dynamic Programming, a problem is divided into sub-problems and the solutions of these sub-problems are combined together to reach an overall solution for the main problem. When using approaches like Divide-and-Conquer, a sub-problem may be solved multiple times. Divide-and-Conquer methods may have to perform more work in these cases.

Dynamic Programming solves each of these sub-problems just once and then saves it, thus reducing the number of computations by avoiding the work of recalculating it again at a later stage, where the solution for that sub-problem is required

Here are some of the most famous problems where dynamic programming is used.

  1. Overlapping Subproblems Property
  2. Optimal Substructure Property
  3. Longest Increasing Subsequence
  4. Longest Common Subsequence
  5. Edit Distance
  6. Min Cost Path
  7. Coin Change
  8. Matrix Chain Multiplication
  9. Binomial Coefficient
  10. 0-1 Knapsack Problem
  11. Egg Dropping Puzzle
  12. Longest Palindromic Subsequence
  13. Cutting a Rod
  14. Maximum Sum Increasing Subsequence
  15. Longest Bitonic Subsequence
  16. Floyd Warshall Algorithm
  17. Palindrome Partitioning 
  18. Partition problem

Backtracking Algorithms
Backtracking = {track for the possible solution and return if it is true otherwise get back and so on}.

In backtracking, we start with one possible move out of many available moves and try to solve the problem, if we are able to solve the problem with the selected move then we will print the solution else we will backtrack and select some other move and try to solve it. If none of the moves work out, we claim that there is no solution to the problem.

Here are some most famous problems where Backtracking approach is used.

  1. Print all permutations of a given string
  2. The Knight’s tour problem
  3. Print all permutations of a given string
  4. The Knight’s tour problem
  5. Hamiltonian Cycle

Advanced details in competitive programming, Check my GitHub repo. Awesome-competitive-programming

You might also like More from author