icodein / competitive-programming-3

This repo contains the solutions of DS and Algo questions

Resources for Competitive Programming

• a2oj
• spoj
• CodeForces
• Codechef
• Hackerearth
• Hackerrank
• InterviewBit
• LeetCode
• cp-algorithms

Guideline: Make account on a2oj with the same username as on codeforces. Join Ladders. If you are a beginner, start with Ladder A.

InterviewBit and LeetCode are best resource for 3rd year students, as mentioned in the last session.

Meanwhile, programmers using C should shift to C++. Those, who are using Java, should keep using it. Python programmers can shift to either of the options. But in my opinion, you should go with C++

Books

• CP Handbook

• GeeksForGeeks

Algorithms

• https://cp-algorithms.com/

---

---------------------------CP ROADMAP---------------------------------

1) Mathematics:

(a)Number Theory

  1) Prime Number Generation (Sieve, Segmented Sieve)
  2) Euler Totient Theorem
  3) Fermat’s Theorem
  4) HCF & LCM (Euclid)
  5) Linear Diophantine Equations (Extended Euclid)
  6) Modulus Arithmetic (addition,multiplication,subtraction,modular Inverse)
  7) Cycle Finding (Floyd Algo and Brent Algo)
  8) Integer Factorization (Trial Division , Pollard Rho method)
  9) Lucas Theorem (Simple & Advance)
 10) Chinese Remainder Theorem
 11) Wilson Theorem
 12) Miller - Rabin Primality Testing
 13) Perfect Numbers
 14) Goldbach Conjecture

(b)Probability

  1) Basic Probability and Conditional Probability
  2) Random Variables
  3) Probability Generating Functions
  4) Expectation
  5) Probability Distribution [Binomial, Poisson, Normal,Bernoulli]

(c)Counting

  1) Pigeonhole principle
  2) Inclusion Exclusion
  3) Special Numbers [Stirling,Fibonacci,Catalan, Eulerian, Harmonic, Bernoulli]
  4) Polya Counting
  5) Burnside lemma

(d)Permutation Cycles

(e)Linear Algebra

  1) Addition And Subtraction Of Matrices
  2) Multiplication ( Strassen's algorithm ), Logarithmic exponentiation
  3) Matrix Transformations [ Transpose, Rotation Of Matrix, Representing Linear Transformations Using Matrix ]
  4) Determinant , Rank and Inverse Of Matrix [ Gaussian Elimination , Gauss Jordan Elimination]
  5) Solving System Of Linear Equations
  6) Matrix Exponentiation To Solve Recurrences
  7) Eigenvalues And Eigen vector
  8) Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial]
  9) Lagrange Interpolation

(e)Game Theory

  1) Basic Concepts & Nim Game [Grundy Theorem , Grundy Number]
  2) Hackenbush

(f)Group Theory

  1) Burnside Lemma
  2) Polya's Theorem

2)Graphs:

(a)Graph Representation

  1) Adjacency Matrix
  2) Adjacency List
  3) Incidence Matrix
  4) Edge List

(b)Graph Types

  1) Directed
  2) Undirected
  3) Weighted
  4) Unweighted
  5) Planar
  6) Hamilton
  7) Euler
  8) Special Graphs

(c)DFS & It’s Application

  1) Cycle Detection
  2) Articulation Points
  3) Bridges
  4) Strongly Connected Component
  5) Connected Component
  6) Path Finding
  7) Solving Maze
  8) Biconnectivity in Graph
  9) Topological Sorting
 10) Bipartite Checking
 11) Planarity Testing
 12) Flood-fill algorithm

(d)BFS & It’s Application

  1) Shortest Path (No. Of Edges)
  2) Bipartite Checking
  3) Connected Components

(d)Minimum Spanning Tree

  1) Prim’s Algorithm
  2) Kruskal Algorithm

(d)Single Source Shortest-Path

  1) Dijkstra
  2) Bellman Ford

(e)All pair Shortest Path

  1) Floyd Warshall’s Algorithm

(f)Euler Tour

(g)Flow

  1) Ford-Fulkerson [PFS,DFS,BFS]
  2) Dinic's Algorithm
  3) Min Cost - Max Flow [Successive Shortest Path Algo,Cycle Cancelling Algorithm]
  4) Max Weighted BPM [Kuhn Munkres algorithm/Hungarian Method]
  5) Stoer Wagner Min-Cut Algo
  6) Hop-Kraft BPM
  7) Edmond Blossom Shrinking Algorithm

(h)Other Important Topics On Graphs

  1) 2-SAT
  2) LCA
  3) Maximum Cardinality Matching
  4) Application Flow
  5) Min Path Cover Over Dag
  6) Independent Edge Disjoint Path
  7) Minimum Vertex Cover
  8) Maximum Independent Set

3) Data Structures:

  1) Arrays
  2) Linked List
  3) Trees (Binary Tree And Binary Search Tree)
  4) Stacks
  5) Queues
  6) Heap
  7) Hash Tables
  8) Disjoint-Set Data Structures
  9) Trie
 10) Segment Tree
 11) Binary Index Tree
 12) Treap

4) Searching And Sorting:

  1) Linear Search
  2) BInary Search
  3) Ternary Search
  4) Selection Sort
  5) Bubble Sort
  6) Insertion Sort
  7) Merge Sort
  8) Quick Sort
  9) Quick Select
 10) Heap Sort
 11) Radix Sort
 12) Counting Sort

5) Greedy:

  1) Classical Problems of Greedy & Concept
     example : Fractional Knapsack

6) Dynamic Programming Classical Problems

  1) Edit Distance
  2) Egg Dropping Puzzle
  3) Integer Knapsack
  4) Largest Independent Set
  5) Longest Biotonic Subsequence
  6) Longest Common Subsequence
  7) Longest Common Substring
  8) Longest Increasing Subsequence
  9) Longest Palindromic Subsequence
 10) Longest Substring Without Repeating Character
 11) Matrix Chain Multiplication
 12) Max Size Square Submatrix With One
 13) Maximum Length Chain Pairs
 14) Maximum Sum Increasing Subsequence
 15) Optimal Binary Search Tree
 16) Palindrome Partition Problem
 17) Set Partition Problem
 18) Subset Sum
 19) Word Wrap Problem
 20) Dynamic Programming Advanced Techniques

DP + Tree DP + Bit Masking DP + Binary Search DP + Graph DP + Matrix Exponentiation DP + Probability Space DP + Crack Recurrence

7) Divide & Conquer

Classical Problems & Concepts

  1) Merge Sort
  2) Closest Pair Points

Other Algorithm Design Techniques :

  1) BackTracking
  2) Man In Middle
  3) Newton-Raphson to reach the fixed point
  4) Brute Force
  5) Constructive Algo
  6) Sliding Window
  7) Pancake Sorting