# 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:
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

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

Sorting algorithms

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:

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.

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

Introduction DFS and BFS:

Minimum Spanning Tree:

Shortest Paths:

Connectivity:

Maximum Flow:

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.

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.

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