The idea is to have a list of hand-picked resources, that can help everyone get into Competitive Programming. Hopefully, will be updated frequently. Suggestions are welcome.
Remember that it is not necessary to go through everything. Pick whatever works for you.
These are the things I know and/or have heard about.
- Let us C - Yashavant Kanetkar
- Computer Science with C++ - Sumita Arora
- CodeWithHarry - C++ Tutorial in Hindi
- Standard Template Library
- Vector
- Iterators
- Pair
- Set/Multiset
- Map/Multimap
- Stack
- Queue
- Deque
- Priority Queue
- List
- Lambda Functions
- Custom Comparators
- STL Playlist
- STL Demo
- Topcoder Blogs on STL
- Setting up a Local Environment
- Text Editors
- Online IDEs (not preferred)
- HackerRank 30 Days of Code
- Hackerearth Basics of Programming
- Hackerrank C++ Practice
- E-Olymp Contests
- Week 1: November 2 – 8. Introduction to C language. Part 1
- Week 1: November 2 – 8. Introduction to C language. Part 2
- Week 2: November 16 – 22. Conditional statement. Part 1
- Week 2: November 16 – 22. Conditional statement. Part 2
- Week 2: November 16 – 22. Conditional statement. Part 3
- Week 3: November 23 – 29. For Loop. Part 1
- Week 3: November 23 – 29. For Loop. Part 2
- Week 4: November 30 – December 6. While Loop. Part 1
- Week 4: November 30 – December 6. While Loop. Part 2
- Week 5: December 7 - 13. Integer arrays. Part 1
- Week 5: December 7 - 13. Integer arrays. Part 2
- Week 6: December 14 - 20. Char arrays 1
- Week 7: December 21 - 27. Char arrays 2
- Week 8: December 28 - January 10. Functions. Part 1
- Week 8: December 28 - January 10. Functions. Part 2
- Week 9: January 11 - 17. Pointers. References
- Week 10: January 18 - 24
- Week 11: February 1 - 7. Linked Lists
- Week 12: February 8 - 14
You can register yourself on these Websites/OJs. They have a huge list of problems to solve and blogs to learn from. Some of them will be referenced later on. They also organise contests, where we can compete with others.
- Hackerrank
- Beginner friendly
- Good place to learn basics
- AtCoder
- AtCoder Beginner Contests (ABCs), as the name suggests, great for beginners
- Codeforces
- Weekly contests (Div. 1/2/3/4)
- Great blogs, everything from basics to advanced
- Codechef
- Cook-Off, Lunchtime (short contests)
- Monthly Challenge (long contest)
- Hackerearth
- Monthly Long Challenge
- Hackathons
- SPOJ
- Classical Problems
- UVa
- ACM-ICPC Problems
- Usually paired up with the book, Competitive Programming 3 - Steven Halim, Felix Halim
- Topcoder
- Amazing blogs
- Topcoder SRMs (short contest)
- CSES Problem Set
- Good introductory problems
- GeeksForGeeks
- Good for Theory and Finding Topics
- Crap implementations dont use them!
- Interview related problems
- Interview Experiences
- LeetCode
- Interview related problems
- Interview Experiences
- Binary Search
- Interview related problems
Important part of CP is to learn algorithms and techniques, practice problems, and to develop algorithmic and constructive thinking.
The best way to progress is to picking an OJ, stick with it and solve problems related to the topics you learn.
Participate in contests and learn from other people.
How to start? Pick first few topics from each heading and learn about them one by one.
- Books
- Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
- Competitive Programming 3 - Steven Halim, Felix Halim
- Competitive Programmer’s Handbook - Antti Laaksonen
- Playlists
- Blogs
- Complexity Analysis
- Look up Heading "Asymptotic analysis (Big-O notation)" in the CodeChef link above
- NPTEL
- mycodeschool's Youtube
- Pashka's Youtube - Algorithms, Time complexity
- GeeksForGeeks - Understanding Time Complexity
- GeeksForGeeks Problem set
- CP-Algorithms
- The On-Line Encyclopedia of Integer Sequences
- PEGWiki
- Competitive Programming 3
- Competitive Programmer’s Handbook
- Ben Qi USACO Notebook
Please use the above Links for reading about the topics mentioned below. The books are extremely helpful for implementation ideas.
-
Graph Theory
- Tree/Graph
- Edges/Nodes
- Edge Classification
- Directed/Undirected
- Degrees
- Colorings
- Weights
- Cycles
- Connected Components/Strongly Connected Components
- Topological Order
- Bipartiteness
- Two-coloring Check
- Konig's Theorem
- Hall's Theorem
- Maximum Bipartite Matching
- Using Flows
- Kuhn's Algorithm
- Spanning Trees
- Tree Diameter
- Tree Isomorphism and Canonical Forms
- Tree Centers
- Planar Graphs
- Euler's Characterstic
- Flows
- Max-Flow and Min-Cut
- Maximum edge disjoint paths
- Maximum independent path / Maximum vertex disjoint path
- Maximum Bipartite Matching on Bipartite graphs
- Minimum edges to be removed to disconnect a graph
- Minimum nodes to be removed to disconnect a graph
- Minimum Path coverage in DAG / Vertex Disjoint Path Cover in DAG
- Minimum Edge cover
- Maximum Independent Set
-
Algorithms
- Graph Representation
- BFS/DFS
- BFS/DFS on Grid
- Topological Sorting
- Minimum Spanning Tree
- Kruskal
- Prims
- Second MST
- Shortest Paths
- Single Source Shortest Path
- Dijkstra
- 0/1 BFS
- Bellman Ford
- SPFA
- All Pair Shortest Path
- Floyd Warshall
- Shortest Paths
- Transitive Closure
- Path building
- SCC
- Counting Paths
- Checking Cycles
- Graph Diameter
- N-Dijkstra
- Floyd Warshall
- Shortest paths with exactly / atmost K edges (min, + multiplication)
- K-th Shortest Paths
- with Dijkstra bounded by visiting each node atmost K times
- Cyclic Graphs
- Eppstein's Algorithm
- Non Cyclic Graphs
- Yen's Algorithm
- Single Source Shortest Path
- Flows
- Travelling Salesman Problem
-
Data Structures
- Disjoint Set Union Find (DSU)
- Segment Tree
- Fenwick Tree (BIT)
- Trie
- Treap
Most of the time it is easier to write Recursion + Memo. It can be converted to iterative later as it supports more optimizations.
- Theory
- Overlapping subproblems
- Optimal substructure
- Types
- Subsets / Subsequences
- Ranges
- Consecutive (Subarrays / Substrings)
- Nested
- General
- Minimization / Maximization
- Counting
- Tracing / Building Output
- on Trees
- Probability
- Bitmasks
- Games
- Optimizations
- Tricks
- Maintain difference of 2 params instead of actual params
- Cyclic Dependencies + Recursion - Set value of DP to base case before recursing
Eveything upto Class XII Maths and more. Discrete Mathematics forms an important part of CP related maths.
- Algebra
- Number System
- Base conversion
- Adders
- Half Adder
- Full Adder
- Number Theory
- Euler's GCD algorithm (and Extended)
- Binary Exponentiation/Multiplication
- Factorisation / Divisors
- Sieve (Linear)
- Powers of Number in n!
- Goldbach's Conjecture
- Linear Diophantine Equation
- Euler's Characterstic
- Mobius Inversion
- Important Sequences/Series/Numbers/Functions
- Binomial Theorem/Pascal's Triangle
- Stirling Numbers First and Second kind
- Bell Number
- Catalan Numbers
- Bertrand's Ballot Theorem
- Reflection Principle
- Euler's Totient Function
- Mobius Function
- Modular Arithmetic
- Basic operations over modulo (+, -, *)
- Modular Arithmetic for Beginners
- Modular multiplicative Inverse (/)
- Fermat's Little Theorem
- Euler's Theorem
- Linear Congruence
- Chinese Remainder Theorem
- Discrete Logarithm
- Combinatorics
- Factorial
- nCr
- 2D Table
- Factorial + Multiplicative Inverse
- Inclusion Exclusion Principle
- Stars and Bars
- Pigeon-hole Principle
- Counting distinct subtrees of a tree
- Geometry
- Trigonometry
- Vector Algebra
- Vector arithmetic
- Sine Law, Cosine Law
- Dot Product
- Cross Product
- Vector Triple Product
- Scalar Triple Product
- Vector Basis
- Gaussian Elimination
- Points
- Euclidean Distance
- Manhattan Distance
- Centroid
- Fermat Point / Geometric Median [UVA 10228]
- Lines
- Equation of Line
- Distance from Point to Line
- Line-Line intersection
- Parametric Form
- Cartesian Form
- Line Segments
- Check Intersection (Cross products)
- Find Intersection (Cramer's Rule)
- Check if point lies on line segment
- Circles
- Equation of Circle
- Construct Circle with 3 points
- Line and Circle Intersection
- Circle Circle Intersection
- Check Intersection (Radii and distances from center)
- Find Intersection (Cosine Rule and Dot product)
- Minimal Enclosing Circle
- Welzl Randomized Algorithm
- Gradient Descent
- Tangent to a circle from a given point
- Polygon
- Properties
- Simple/Non Simple
- Convex/Concave
- Square
- Check if 4 points form a square
- Polygon Area
- Point inside polygon
- Winding Number Rule
- Polygon Centroid
- Polygon Decomposition (into Triangles)
- Polygon Cut by line
- Polygon inside polygon
- Repeatedly cut one polygon by other polygon
- Shortest Distance between 2 polygons
- Properties
- Closest Pair of Points problem
- Probability / Statistics
- Mean, Median, Mode
- Bayes' Theorem
- Random Variable
- Expected Value
- Linearity of Expectation
- Matrices
- Matrix operations
- Determinant
- Cofactors
- Cramer's Rule
- Solving System of Linear equations
- Matrix exponentiation
- Hadamard Matrix
- Searching
- Binary Search
- Topcoder - Discrete Binary Search
- Errichto - Binary Search
- Errichto - Binary Search Various Implementations
- Ternary Search
- Binary Search
- Game Theory
- Optimal Move
- Winning/Losing State
- Dependence on Initial/Final State
- Mathematical Circles: (Russian Experience) - Dmitrii Vladimirovich Fomin and Sergei Aleksandrovich Genkin
- Theory
- Substrings
- Subsequences
- Palindromes
- Algorithms
- Prefix/Failure Function
- String Matching
- KMP
- Rabin-Karp
- String Hashing
- Data Structures
- Trie
- Difference array, range updates in O(1)
- Largest Rectangle in Histogram
- Median of running data with 2 Heaps
- Powers of Number in n!
- Largest Area in a room from where we can see all walls
- Calculations involving multiplication/division (like Factorial) can be written in Prime exponent form
- Building Prefix array instead of actual array in case of XOR problems