# Competitive Programming: From Beginner to Expert

March 16, 2017

This is a very comprehensive 94-part course on competitive programming. It gets you from knowing basic programming to being a yellow-red rated coder on Codeforces / CodeChef / TopCoder / etc.

The **primary objectives** of this course are to learn about 30 different algorithms and data structures. The algorithm tutorials include short intuitive video tutorials, as well as links to a more in-depth text tutorial.

We’ll solve 1-2 problems for each topic, and many more for the popular and versatile topics such as dynamic programming and graphs. Each problem includes hint-by-hint solutions from a problem solving point of view, which sharpens your problem solving skills even if you aren’t able to solve the problem on your own.

**Expected time to completion**: 60-90 sessions. 2-3 months if you make progress daily, 4-6 months if you come 2-3 days per week. Each problem will teach you something new, so make sure you understand it before moving on.

This course focuses more on solving problems using the algorithms. For a stronger foundation in algorithms and data structures, I recommend doing the following course: Learn Algorithms and Data Structures.

**Pre-requisites**: Basic knowledge of any programming language. If you don’t have the pre-requisite, you should start here: C++ / Java / Python for Competitive Programming.

# Introduction to Algorithms and Problem Solving

- Why do we need (efficient) algorithms?
- Quiz: Analyzing code complexity, estimating runtime and memory usage
- Quiz: Asymptotic notation and functions
- [LEADGAME] Lead Game
- [ZCO14001] Video Game (ZCO 2014: India)
- [VOTERS] Voters List
- [ZCO12001] Matched Brackets (ZCO 2012: India)

# Recursion + Quick-sort + Merge-sort

- Introduction To Recursion
- Quiz: Recursion
- Quick-sort: Video tutorial, pseudo-code (and in-place sorting)
- [ZCO15002] Variation (ZCO 2015: India)
- [ZCO12002] Wormholes (ZCO 2012: India)
- Merge-sort: Detailed tutorial with Python & C++ implementation
- [INOI1201] Triathlon (INOI 2012: India)
- [Codechef COOK82C] Hussain Set
- Quiz: Recursion (Hard)

# Binary search (+ extras)

- Binary search: Video tutorial, code and extensions
- Binary search extended
- [SPOJ AGGRCOW] Aggressive cows!
- [INOI1501] Special Sums (INOI 2015: India)

# Greedy Algorithms

- Greedy Algorithm
- [TADELIVE] Delivery Man
- [CLETAB] Cleaning Tables
- [GCJ101BB] Picking Up Chicks
- [CROFT] The Crofts Game

# Dynamic Programming

- Dynamic Programming
- [ZCO14002] SUPW (ZCO 2014: India)
- [ZCO12004] Round Table (ZCO 2012: India)
- [INOI1301] Calvins Game (INOI 2013: India)
- Dynamic Programming (continued)
- [AIBOHP] Aibohphobia
- [ALTSEQ] Alternating Sequences
- [INOI1401] Highway Bypass (INOI 2014: India)
- [IOI 2000] Palindrome
- Quiz (hard): The Knapsack problem, and Dynamic Programming
- [BAT2] Batman2
- [LVADER] Luke vs Darth Vader
- [RENT] Rent your airplane and make money

# Heaps and Heap Sort

- Heaps and Heap-sort
- [INOI1202] Table Sum (INOI 2012: India)
- [RMID2] Running Median Again
- [LAZYPROG] The lazy programmer

# Graph algorithms

- Introduction to Graphs (and how to represent them)
- Standard Template Library (and adjacency list implementation)
- [CYCLEPERM] Permutation Cycles
- Breadth-first search and Depth-first search
- [INOI1601] Wealth Disparity (INOI 2016: India)
- [INOI1302] Sequence Land (INOI 2013: India)
- [659E] New Reform (Graph Problem)
- [Hackerrank] Roads and Libraries
- [Hackerrank] Journey to the moon
- Dijkstra’s algorithm (Shortest path algorithm)
- [SHPATH] The Shortest Path
- [OI10SUM] Sums (POI 2010: Poland)
- Single Source Shortest Path: Bellman Ford
- [UVA 11721] Instant View Of Big Bang
- All Pairs Shortest Path (Floyd Warshall)

# Matrix Exponentiation

# Graph algorithms continued

- SPOJ RDNWK: Road Network
- [CNTTREE] Trees Again
- Prim’s algorithm for Minimum Spanning Tree
- Correctness of Prim’s algorithm and Kruskal’s algorithm
- Minimum Spanning Tree implementation practice
- [IITWPC4I] Petya and Repairment of Roads
- HackerRank Week Of Code 31: Spanning Tree Fraction
- Centroid Decomposition in Trees Tutorial
- [IOI2011] Race
- Codeforces 321C: Ciel The Commander
- Dynamic Programming on Trees (or Tree DP)

# Segment Trees (including extensions) + Binary Indexed Trees + MO’s algorithm + HLD

- Segment Trees
- [SUMSUM] Enjoy Sum with Operations
- [GSS1] Can you answer these queries 1
- [FREQUENT] Frequent values
- Augmented Segment Trees
- [TEMPLEQ] Temple Queues
- [SALMAN] Salary Management
- [QTREE7] Query on a tree VII
- Binary Indexed Trees (aka Fenwick Tree)
- [FENTREE] Fenwick Trees
- Merge Sort Trees
- Persistent segment trees: Explained with SPOJ problems
- MO’s Algorithm (Query square root decomposition)
- Sqrt-Decomposition Tutorial
- [DYNACON2] Dynamic Graph Connectivity
- Heavy Light Decomposition