Section 0 : Introduction	Section 1 : Basic Theory	Section 2 : Intermediate	Section 3 : Advanced
Introduction	Number Theory	Advanced Maths	String Hashing
Getting Started	Two Pointers / Sliding Windows	Range Update Queries	Directed Graphs
basic prob solving	Range Queries	Graph Theory Basics	Range Update
Time Complexity	Divide and Conquer	DSU + MST	Sparse Table
Intro To STL	Intro to Greedy Algorithms	Shortest path	Tree Algorithm
Sorting	Dynamic Programming
Binary Search	Interactive Problems
Bit Operations
Number Theory
Recursion
Complete Search

Section 0: Introduction :

What is CP and Why do it?

It's a mind-sport where you are given a problem and have to come up with optimized solutions for the given constraints with your problem-solving skills and implement with your coding skills.
We do it because it helps us in building our logical and analytical thinking skills and also in enhancing our knowledge. But most importantly, because it’s a lot of fun! (and it helps get a job 👀)

Some Popular CP Platforms are

- Codeforces - Codechef - Topcoder	- Atcoder - Leetcode - Hackerrank

We will look into them further as we go on!

➡️Getting Started

Learn C++ :

If you have already gone through ESC112( any Coding Course in C) then you may follow this article for a smooth transition : Moving from C to C++
If you have no prior coding experience , you can follow :
- For youtube fans :(They also have a guide to setup)
  1. Bro Code : [first 5 hours]
    OR
  2. Free Code Camp : [first 3 hours]
- If you prefer to read, then :
  1. USACO : PAPS(book Chapter 2)
    OR
  2. Learn C++ (Just the intro and functions parts)
Register on CodeChef ; and then solve the given problems :
- Codechef - GDTURN
- Codechef - TAXES
In the end, you truly learn the language after you have sufficient experience. Try out as many problems from these links :
- Beginner Problems | Codechef

Setting Up Environment :

We prefer VS CODE because of obvious reasons , still feel free to use any other usable Code Editor like : sublime text , codeblocks , etc.

Windows : you can watch the same video from above from [0:1:27] to [0:8:40]

Currently you will be able to work fine with #include<iostream> , but in future if you’re facing issues with #include<bits/stdc++.h> on VS code then watch this video.
Mac : Download and install VS Code from https://code.visualstudio.com/ and then Set it up for C++. After this, it is best to change your compiler to gcc.
You can follow this tutorial to install gcc.

➡️Basic Problem Solving

Your first problem on Codeforces
Starting with a less interactive platform like CodeForces can be difficult, but don't worry we got your back :
1. start by registering yourself on https://codeforces.com/
1. Here's Everyone's First Problem, have a look
1. Head to your local IDE
1. When you pass the sample inputs locally, click on Submit.
1. You can paste your entire code to the Source Code section (OR upload your solution.cpp file) and press Submit.
PS : We recommend enrolling yourself in the "ITMO Academy: pilot course" on Courses - Codeforces. It contains great problems as well as theory which we'll cover as we move forward. By the end of the roadmap, you can independently finish it !
More problems from CodeForces
Your first problem on CSES
CSES is a problem set : register yourself
1. Link : Problem 1 ; here you can only submit the solution as a file. Head to your local IDE and write up a 'solution.cpp'
1. Run locally and check the code
1. Press on the Submit tab and Upload the code file. The results of Online Judge will be displayed in some time.
1. Make sure to use long long int ;)
Your first problem on SPOJ.com : Problem TEST

Fast I/O (optional for now):

What it is :

Try this problem with Fast I/O :

Enormous Input and Output Test - SPOJ INOUTEST - Virtual Judge

Your First Problem on USACO
About USACO :
1. USACO has problems revolving around Farmer John's Farm and (mostly) His Cows.
2. Make a new account here. Whenever you go to a problem, you can press the 'Overview' tab to head to the same page for logins.
3. You can only submit the solution as a file; apart from that you might be required to get input from a file , output your answer to a file (all that will be processed on server).
4. Ex : mixmilk.in for input and mixmilk.out for output. Then you need to add these lines at the start of your code:
```
freopen("mixmilk.in", "r", stdin);freopen("mixmilk.out", "w", stdout);
```
(know more about it here / official page )

Or you may make your template for USACO problems like :
Template - (Fast I/O included)
```
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void setIO(string s){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int main(){
    setIO("mixmilk");


    return 0;
}
```
First Problem
1. Link : Mixing Milk ; Head to your local IDE and write up a solution.cpp.
2. Create mixmilk.in locally in the same folder as your solution.cpp; enter sample input in it (treat .in and .out as .txt files).
3. Run locally and check the code.
4. Upload the file, Select C++11, Submit. The results of Online Judge will be displayed in some time.
More problems on USACO :
- Shell Game
- The Bovine Shuffle

Basic Math Problems

CF - Panoramix's Prediction

CF - System of Equations

CF - GCD vs LCM

CodeChef - Two equations

Some suggestions from the Makers :

We believe that a lot of practice is what shapes you in CP ; apart from the questions found here , it is suggested to practice more problems whenever you feel.

It is sometimes okay to look up the solution / editorial (for codeforces). Don't fret if you're not able to solve a problem, you'll get it with practice.

The " Expected time" is the amount of time you will need to give to prepare the theory in a heading before practicing.

Take your time to understand things and implement them. The expected time is suggestive and varies from person to person, but do not spend too much time on a single topic.

Consistency is very important in CP. It is highly recommended that you keep practicing it at your own pace daily, rather than doing it all at once. It is a skill that develops over time.

➡️Time Complexity

Expected time : 40 - 50 minutes

Solve these in O(n) :

CSES : Missing Number

CodeChef - Magician versus Chef

CSES : Increasing Array ~~Make sure to use long long int ;)~~

CSES : Permutations

➡️Intro to STL

Expected time : 40 - 60 minutes

Basic Array / Vectors Problems

CF - Team

CF - Series of Crimes

CF - Beautiful Matrix

CF - I Wanna Be the Guy

CF - Game Outcome

Basic String Problems

Your intro to strings : C++ Strings (With Examples)
- CF - Boy or Girl
- CF - LLPS
- SPOJ.com - Transform the Expression
- CF - Phone Code ( use vector<string> 👀)
Basic Stack Problems

➡️Sorting

Expected time : 2 - 2.5 hours

CPH page 25 Read Chapter 3 from ‘Competitive Programmer’s Handout’
Sorting Algorithms | LeetCode The Hard Way (optional)
Tutorial with Visualisation

problems :
- CSES : Apartments
- CF - Assembly via Minimums
- CF - Progressive Square
- CF - XOUR - A bit on the mathematical side, think about using map<int,vector<int>> .
- CSES : Collecting Numbers
- CSES : Tasks and Deadlines

➡️Binary Search

Expected time : 40 - 60 minutes

Tutorial with Visualisation
Binary Search | Code Accepted
- ITMO - First Implementation
- CF - Cat, Fox and the Lonely Array
- ITMO : Application on real numbers
- CSES - Array Division (Minmax concept)
- CF - Maximum Median
Alternative Soln Link

Binary Search · USACO Guide
Additional Practice

➡️Bit Operations

Expected time : 1 - 1.5 hours

Problems :

➡️Primary Number Theory

Expected time : 1 - 1.5 hours

Binary Exponentiation

Expected time : 20 - 30 minutes

Factorisation [till O(rootN)]

Expected time : 20 - 30 minutes

Primality Testing | Code Accepted

we’ll cover Sieve of Eratosthenes later*
Trial division

Gcd

Expected time : 20 - 30 minutes

Greatest Common Divisor | Code Accepted
Gcd
More Practice
- Codechef - Hello Equation
- Codechef - Bitwise Equation

➡️Recursion

Expected time : 1.5 - 2 hours

C++ Recursion (With Example)
The classic recursion problem : Tower of hanoi or Video
Read this article on recursion (you may skip the introduction ) . CSES : Chessboard and Queens try this question which is an extension of the N Queens Problem .

Basic Recursion problems:
- CSES : Weird Algorithm
- CSES : Elimination Game
- CSES : Apple Division
- CSES : Creating Strings - Try generating all possible permutations using recursion

➡️Complete Search

Expected time : 1.5 - 2 hours

Problems:
- Creating Strings - try without using next_permutation() ;)
- Virtual Judge - Bars
- CF - Creating Expression1
- CF - 2D Traveling
- USACO - Air Cownditioning II
- CF - Reverse String

By now, you may have realized that debugging your code efficiently is very important. For a few tips on debugging, you can go through this article / this video.

➡️Section 0 Additional Practice:

SPOJ.com - Factorial

SPOJ.com - Small factorials sometimes one has to use python in CP :)

SPOJ.com - Transform the Expression

CF - Turtle and an Infinite Sequence

CSES : Sum of Three Values

CF - Chat Order

CF - Cellular Network

Section 1: Basic Theory

➡️Number Theory

Number Sieve

Expected time : 1 - 1.5 hours

(Sieve of Eratosthenes - Wikipedia)
or
(Sieve of Eratosthenes - CpAlgorithms )
- Count Primes - LeetCode
- SPOJ.com - Problem NFACTOR
Faster Prime Factorisation
- CSES : Counting Divisors : attempt it and have a look at this solution or
- Prime Factors in Log(N) Tutorial | LeetCode The Hard Way :::

Problems :

Modular Multiplicative Inverse

Expected time : 20 - 30 minutes

Modular Multiplicative Inverse | forthright48

Virtual Judge - Modular division

CSES : Exponentiation II

Additional Practice :

Codechef - GCD of Prefixes

SPOJ.com - Distinct Primes

Codechef - Modular GCD (you might wanna use (__int128_t))

CSES : Divisor Analysis

CF - Orac and LCM

CF - k-LCM (hard version)

CF - Santa's Bot

Codechef - Chef and Riffles (Here’s a challenging problem to practice binary exponentiation)

Hint

In essence, you need to apply the permutation U = (1, 3, 5 … N - 1, 2 , 4 …. N) to your initial array K times which is the same as composing f with You can use binary exponentiation). :::

➡️Two Pointers / Sliding Windows

Expected time : 30 - 40 minutes

CPH
video
Problems
Additional problems
- CSES : Subarray Distinct Values
- CSES : Sum of 4 values
- CF - Quiz Master(try coming back to this question after you learn about sieve method)

➡️Range Queries

Prefix Sums are Intensively Used in other problems to reduce Time Complexity of Solution.

Expected time : 40 - 50 minutes

CPH Range Queries (before Binary Indexed Tree)
USACOBOOK ch11 Prefix Sums
Solved Examples Leetcode two solved illustrations; more problems to solve.
Maximum Sum Subsection

Problems :
- CSES : Maximum Subarray Sum :
  
  Hint
  
  search for Kadane’s Algorithm

2 D Prefix Sum
- Ramu's Mango Trees
- CSES : Forest Queries
- Aizu Online Judge - Maximum Number of Overlaps

Additional Practice

USACO - Subsequences Summing to Sevens

CF - Data Structures Fan

CSES : Subarray Divisibility

➡️Divide and Conquer

Expected time : 20 - 30 minutes

Read this to know what divide and conquer is. Watch this video to get more insight into this topic

CF - Lost numbers

CF - Print the pattern

CF - Permutation Transformation

CF - Maximum Crossings

CF - Greetings

➡️Intro to Greedy Algorithms

Expected time : 1.5 - 2 hours

Moving in the direction which gives the most optimal solution at every step is a major characteristic of these algorithms.

Read Greedy Algorithms - CPH and Job Scheduling to get a better idea of these algorithms . Greedy | LeetCode The Hard Way
Alternatively, you may go through this video.

Here are some questions :

CF - Studying algorithms - An easy problem to start with

Optimal Merge Pattern - Involves the use of multiset/priority queue

SELF ASSESSMENT :

CF -Heavy Intervals

CF - Contrast Values

CF - Grid Reconstruction

CSES - Ferris Wheel

CSES - Movie festival

CSES - Towers

CSES - Movie festival 2

➡️Dynamic Programming

Basic Concepts :

Dynamic Programming , more famously known as DP is a technique in which we calculate and store subproblems in a particular problem.

There are two methods to apply dp in your code : recursion and iteration .

Expected time : 1.5 - 2 hours

This video explains the difference between the two implementations for fibonacci numbers, then try this problem :
- CSES : Dice Combinations
Read Chapter - 7 CPH
Classic Solved Illustrations

After completing above resources for DP , you can now do the following standard problems :
- Longest Increasing Subsequence - LeetCode
Video Solution

Youtube
- Longest Common Subsequence - LeetCode
Video Solution

Youtube

DP on Grids :

This tutorial has some generic problems which will develop your understanding about grids .

CSES : Grid Paths ( A tougher version of counting number of paths from one corner to another )

Superjump in a grid- Another variant of path counting problem

LeetCode - Cherry Pickup-2 ( Here we have 2 sources , different as compared to other questions , think about dp-states) [TOUGH QUESTION]

DP Bitmask :

Expected time : 1.5 - 2 hours

Read this blog ( it is based on the CP book of Felix & Halim ) to begin with bitmasking . Follow this tutorial for further understanding .
More resources - Advanced DP concepts (you may follow up to 45:00 )
Some Problems :

DP is a topic which can be mastered only through practice.

Some resources for practice :
- AtCoder DP Contest
- CF Problemset (Use tag=dp in filters )
- CSES Problem Set (DP section)

SELF-ASSESSMENT ( Topic : DP )

CF - Nikita and String

CSES : Coin Combinations - 1 ( You can also try Coin combinations-2 on CSES )

CF - Counting Rectangles

CF - Marvalo Gaunt's Ring

CSES : Rectangle Cutting

CF - Woodcutters

CF - Tetrahedron

Extra

There exist both dp and math based solutions , the math solution can be found if you know about recursive relations and how to find their solutions using quadratic equations , this solution has a time complexity of O(log(n)) and uses binary exponentiation

CF - Long Path

Extra

There are two dp solutions one having O(n) time complexity and the other being O(n^2) .. which one were you able to spot

Some Question on Dp + Probability and expected values :
- CF - Bad Luck Island
- CF - Jeff and Furik
Interestingly you can solve this question even without dp but this solution still demands generalizing the solution , can you spot this
- Atcoder - Sushi

➡️Interactive Problems

Expected time : 15 - 20 minutes

Here is a tutorial on how to solve interactive problems .

Here are some questions :

CF - Interview

CF - Guess The Array

CF - Bit Guessing game (Involves bit manipulations )

Some more tools to help you in your journey :

Diffchecker - some problems have large output files. Use this tool to compare your generated output and problem's expected output.

CodeForces Chrome Extensions :

CF Analytics - improves the Codeforces profile webpage to include statistics of problems solved by the user.
CodeForces Enhancer - multiple ratings graph, adds "Hide/Show solved problems" link to Problemset page
Carrot - predicts actual performance in the contest, how many rating points you will gain after the contest, etc.
Conding Dude - Contest Reminder

➡️Section 1 Additional Practice:

CodeChef - Mathison and the Dynamo shuffle

CF - Long Multiplication

SPOJ.com - Eko

LeetCode : Container with Most Water

CF - Final Boss

SPOJ.com - ABCDEF

CF - Update Queries

CF - Forming Triangles

CF - Binary Search

CF - Inaccurate Subsequence Search

Section 2: Intermediate

➡️Advanced Maths

Combinatorics

Expected time : 15 - 20 minutes

Read the following topics : Binomial Coefficients , Catalan Numbers
Refer CPH Ch 22 for further reading
Some questions :
- DPL_5 < Library < Courses | Aizu Online Judge (all 12 types of cases)
- Virtual Judge - One Unit Machine
- CSES : Christmas Party
- CF - Secret Box
Some additional Problems:
- CF - Earning on Bets
- CF - How does the rook move?(try using your DP skills here)
- CF - Blueprint for Seating
Hint

This may be tough but if you can, try thinking about all the valid permutations. Trust me you’ll be very happy if you figure the answer out ;-)

Matrices

Expected time : 1 - 1.5 hours

For learning about the implementation of basic operations on matrices read CPH Ch23.
- A few ad hoc problems based on matrices-
  - CF - Weird Sum
  - CF - Permutation on rows and columns
Read this Blog | CodeForces or Matrix Exponentiation | Code Accepted , it would help to solve recurrence based questions using matrices .
Matrix Exponentiation tutorial + training contest | CodeForces
- Some problems on Matrix Exponentiation:
  - CSES : Fibonacci Numbers
  - CF - Random Mood
  - { the following two problems require basic graph theory } :
  - CSES : Graph Paths I ; you may refer this for a hint.
  - AtCoder - Walk
  - CSES : Graph Paths II

Probability

Expected time : 1 - 1.5 hours

Extra Number Theory

Expected time : 1 - 1.5 hours

CPH Ch 21
Solving system of congruences | AlgorithmClear Blog
Some more problems :
- SPOJ.com - Euler Totient Function Depth

➡️Range Update Queries

Expected time : 1.5 - 2 hours

CPH Range Queries (may skip Fenwick Tree, as Segment Tree is able to do anything one can do with Fenwick Tree)
Segment Trees
- CS Academy Tutorial OR
- CP Algorithms Tutorial (only read Simplest form of a Segment Tree for now)
Fenwick Trees (optional ; may read just for knowledge)
- CS Academy Tutorial OR
- CP Algorithms Tutorial

Let’s get started with practice :
- ITMO step 1 theory read the article below / watch videos 1,3 for the same content
- ITMO - Segment Tree for the Sum for solution : watch a video with the title ‘CODE 1’ on above link
- CSES - Segment Tree for the Minimum
- ITMO - Number of Minimums on a Segment soln : CODE 2 on above link
- SPOJ.com - Range Sum
- CF - Thor
ITMO step 3 go through theory , problems , solutions in order; then solve :

➡️Graph Theory Basics

Expected time : 40 - 60 minutes

Here is a brief intro to graphs and its representation.
You may also refer Representation of Graphs | Code Accepted, then solve this problem :

Spoj - ROADNET

Here’s a video if you prefer those : Introduction to Graph Theory: A Computer Science Perspective

BFS and DFS

Expected time : 30 - 40 minutes

There are two basic (and extremely useful) algorithms for graph traversal : BFS and DFS.
To understand them, read page number 117 to 122 from this handbook.
Or we recommend watching these videos :
- Depth First Search (DFS) Explained: Algorithm, Examples, and Code
- Breadth First Search (BFS): Visualized and Explained (Also has the flood fill problem!)
Here are some problems :
- CSES - Message Route
- CF - Two Buttons
- USACO - Moocast
- CF - Kefa and Park
- CF - Round Dance
- CSES - Building Teams (Question on bipartiteness)

Cycles Detection

Expected time : 20 - 30 minutes

This and This article will help you understand how to find cycles.
Problems :
- CSES : Round Trip
- CSES : Round Trip II
Other problems for bidirectional graphs :
- SPOJ.com - Cactus : use unsigned long long int ;)
- CF - Forest Program

Bridges in Graphs

Expected time : 30 - 40 minutes

[Tutorial] DFS TREE | CodeForces
Problems :
- Critical Edges
- Bertown roads

Flood Fill

Expected time : 15 - 20 minutes

To understand flood fill, you can go through this article. It was also covered in the video above.
Problems:
- LeetCode : Flood Fill
- CSES : Counting Rooms

Topological Sort

Sorting nodes of a directed graph in an order in which they can appear in a path.

Note : we can only find topological sorting for an acyclic directed graph.

Expected time : 40 - 60 minutes

You can read this or watch this to understand topological sort.
CPH 16.1
There is also Kahn's Algorithm
Here are some problems:

Number of topological sortings for a directed tree is discussed in Section 3 Tree Algorithms : DP on Trees

Subtree/DFS Problems

try these problems
- CSES : Subordinates
- CF - Journey
- LeetCode - Binary Tree Maximum Path Sum
- Codechef : Chef and Subtree MEXs (hint : Problem Subordinates)

➡️DSU + MST

Disjoint Set Union

Expected time : 1.5 - 2 hours

DSU is a data structure that allows us to combine two sets, find out which set a particular element belongs to and allows us to create a set from a new element.
This video lecture will help you understand it well!

Minimum Spanning Trees

Expected time : 1 - 1.5 hours

PAPS Section 12.4
How Do You Calculate a Minimum Spanning Tree?
CPH OR
Read these articles : Kruskal , Kruskal DSU , Prim's Algo OR
Go through these videos : Kruskal using DSU , Prim's Algo

Practice :

➡️Shortest Path Algorithms - Dijkstra, Floyd Warshall, Bellman Ford

Expected time : 1 - 1.5 hours

You can go through Ch - 13 of this book for better understanding or if video lectures are more up your alley, you can watch these : Dijkstra, Bellman Ford, Floyd Warshall.
Problems :
- CSES : Shortest Routes I (Djikstra)
- CSES : Shortest Routes II (Floyd Warshall)
- CSES : Flight Discount
- CSES : Cycle Finding (Bellman Ford)
- LeetCode - Path with Maximum Probability
- USACO : Milk Pumping

➡️Section 2 Additional Practice:

CSES : Distributing Apples

CSES - Prime Multiples

CSES : Graph Girth

CF - Labyrinth (you can use 0-1 BFS)

CF - Cyclic Components

CF - Number of Simple Paths

CF - Arrayland's Challenge - On the tougher side

CF - Lonely Mountain Dungeons

SPOJ.com - Fibonacci Sum

CF - Turtle Mission: Robot and the Earthquake

CF - Friendly Spiders

CF - GCD and MST

CF - Split Into Two Sets

Optional :

Bacterial Sampling - Find the Z matrix of the recursion - Time complexity O(log(n)) with a constant of 20*20

Section 3: Advanced

➡️String Hashing

Expected time : 2 - 2.5 hours

Read ch 26 to get an overview of string algorithms like hashing, z-algorithm and trie structure.
Refer to this video for a detailed explanation. It also explains algorithms like Knuth-Morris-Pratt (KMP) algorithm.
This article covers Aho-Corasick algorithm
Problems :

➡️Directed Graphs

Expected time : 1.5 - 2 hours

A directed graph is a graph where the edges have a direction.
Theory on Directed Graphs : CPH Ch 16

Codechef - MaxEdges

LeetCode - Minimum Number of Vertices to Reach All Nodes

Cycles in Directed graphs

Functional Graphs

Graphs where each node has exactly one outgoing edge (outdegree = 1)
- CSES - Planet Queries I , use : CPH 16.3
Cycle Finding :
1. We can use Floyd's Cycle Finding Algorithm + Visualization also known as Tortoise and Hare Algorithm
2. We can also use Kahn's algorithm
In Kahn's Algorithm : If all nodes in the graph are not removed as zero degree -> it implies that there must be cycles.
Solve the following problems involving cycles: (a graph with vertices = n and edges >= n will have atleast one cycle)
- USACO - The Bovine Shuffle
- USACO - Visits
- CSES - Planets Cycles
  or
- Atcoder - Reachability in Functional Graph
  {both problems have the same answer}
- CF - Secret Santa

Strongly Connected Components :

A part of graph (component) is said to be strongly connected if there is a path from any node to all other nodes in the component.

In Function Graphs : Every cycle alone is a SCC;

Generally : if two cycles share a vertex they both come under the same SCC.

Start with CPH Ch 17 ; Learn any of these algorithms to solve problems
1. Kosaraju's Algorithm
  - Techdose - Youtube
  - CP Algos Article
2. Tarjan's Algorithm
  - William Fiset - Youtube
  - Tutorial | CodeForces
Try these problems :

If you make disjoint sets of vertices within a SCC and join edges connecting SCCs; you get a Condensation Graph. This graph does not contain cycles as in that case they would form another SCC. Thus it's a Directed Acyclic Graph.

Problems involving more ideas like condensation , topological sort :

2-SAT

Go through one of these
Attempt these problems
- CSES : Giant Pizza
- CF - Problem H ±1

DP on DAGs

DAGs stands for Directed Acyclic Graphs, Trees are a particular kind of DAG.

Try this simple problem to start with :

AtCoder - Longest Path

Then read CPH 16.2 and DP on Trees and Graphs | CSE 421
If you prefer to watch some videos :
- MultiStage Graph | Abdul Bari - Youtube
- Shortest/Longest path on a DAG - WilliamFiset | Youtube
Problems :
DP on Trees

➡️Range Update Queries (continued)…

Expected time : 1.5 - 2 hours

This topic is continued from the previous section.

Try this problem : CF - Xenia and Bit Operations
More Complex Queries ( Continued from earlier CP - Algos article)
ITMO Step 2 - Go through theory, problems, solutions in order then solve :

Additional (optional) :

ITMO step 4 (no video solutions)
- CSES - Increasing Subsequence II (hint : step 3)
Range Update Seg Tree , ITMO step 5
Range Queries in two Dimensions
- Read CP Algorithms article / TopCoder article
- SPOJ.com - Matrix Summation
- CSES - Forest Queries II
Number of distinct integers in O(log N) - Stack Overflow
- CSES - Distinct Values Queries (unique problem)
Longest increasing subsequence - CPAlgorithms solution with data structures

➡️ Sparse Table

Expected time : 1 - 1.5 hours

Video / Theory
Problems :
- CSES - Static range minimum query
- CF - Ant colony(maybe slightly tough)
- CF - Longest Regular Bracket Sequence
- CF - CGCDSSQ
- CF - Turn off the TV
The same idea can be applied for 2D Range minimum queries as well. Here is a blog that explains it.

➡️Tree Algorithm Problems

Expected time : 2 - 2.5 hours

CPH Ch 14 / Tree Algorithms - YouTube / AlgorithmsThread 8: Tree Basics

Tree Diameter

You can go through this Article / this Blog (CodeForces)
- CSES - Tree Diameter
- CF - Gym Problem 1 ( video solutions for Gym : Tree Basics Solutions )
- CSES - Tree Distances I
- CF - Gym Problem 2
- CF - Minimize the Diameter

DP on Trees

(this section builds on from DP on DAGs)

Here’s a blog on DP on Trees
Here are some specific problems on Trees :
Number of Topological Sorting :
- [Blog] Number of Topological Orderings of a Directed Tree | Codeforces
- CodeChef - Build Towers

Tree Queries

CPH 18.1 Finding Ancestors + Binary Lifting - CPAlgorithms
CPH 18.2 Subtree and Path Queries / Euler Tour
CPH 18.3 Lowest common ancestor + Lowest Common Ancestor - CP Algorithms + WilliamFiset | Youtube
More Problems:
- SPOJ.com - Query on a tree II
- Optimal Connectivity try with binary lifting ;)

➡️Section 3 Additional Practice:

CSES - Pizzeria Queries

CSES - Salary Queries

CSES - Planet Queries II

CSES - Tree Distances II

CSES - Counting Paths

CF - Shuffling Songs

CF - Sasha and Array

CF - Analysis of Pathes in Functional Graph

CF - Count Paths Queries

CF - Civilization

LeetCode - Binary Tree Cameras

SPOJ.com - Cost

Additional Topics

Convex Hull Trick, Square Root Decomposition, DP Optimizations (Knuth, Aliens, Divide and Conquer, CHT), LiChao Tree, Mo’s Algorithm, Digit DP, Broken Profile DP, Connected Components DP, DP on Trees, Sparse Segment Trees, Persistent Data Structures, Slope Trick, FFT, Suffix Array, Tries, Heavy Light Decomposition, Centroid Decomposition

NOTE : For the topics we covered above there still exist a lot of variations which might be missed out by us or were not possible in the scope of this Roadmap.

Continue your jouney in CP with self exploration !

➡️ Some More Resources -

✧ Books -

✧ Problem Sets and Resources -

ITMO Academy: pilot course - Codeforces (Recommended)
USACO Guide (Recommended)
The Ultimate Topic List
CSES Problem Set
A2OJ Ladders
AtCoder Problems
CP-Algorithms
KACTL CP Templates C++
T-414-ÁFLV: A Competitive Programming Course
Archived Problems - Project Euler (if you’re into math ; improves problem solving)
Number Theory Articles | Brilliant

✧ Blogs -

✧ YouTube Channels and Playlists -

This roadmap could never be possible without the inspiration and background support of the Makers of the Previous Roadmap :

Sanat Goel
Vipul Chanchlani
Goutam Das
Rishi Agarwal
Varun Tokas
Shivam Mishra
Chayan Kumawat
Prerak Agarwal
Sankul

Competitive Programming Roadmap

Contents :

Section 0: Introduction :

What is CP and Why do it?

➡️Getting Started

Learn C++ :

Setting Up Environment :

➡️Basic Problem Solving

Fast I/O (optional for now):

Basic Math Problems

Some suggestions from the Makers :

➡️Time Complexity

➡️Intro to STL

Basic Array / Vectors Problems

Basic String Problems

➡️Sorting

More on STL

➡️Binary Search

➡️Bit Operations

➡️Primary Number Theory

Binary Exponentiation

Factorisation [till O(rootN)]

Gcd

➡️Recursion

➡️Complete Search

➡️Section 0 Additional Practice:

Section 1: Basic Theory

➡️Number Theory

Number Sieve

Modular Multiplicative Inverse

Additional Practice :

➡️Two Pointers / Sliding Windows

➡️Range Queries

Additional Practice

➡️Divide and Conquer

➡️Intro to Greedy Algorithms

SELF ASSESSMENT :

➡️Dynamic Programming

Basic Concepts :

DP on Grids :

DP Bitmask :

SELF-ASSESSMENT ( Topic : DP )

➡️Interactive Problems

Here are some questions :

➡️Section 1 Additional Practice:

Section 2: Intermediate

➡️Advanced Maths

Combinatorics

Matrices

Probability

Extra Number Theory

➡️Range Update Queries

➡️Graph Theory Basics

BFS and DFS

Cycles Detection

Bridges in Graphs

Flood Fill

Topological Sort

Subtree/DFS Problems

➡️DSU + MST

Disjoint Set Union

Minimum Spanning Trees

➡️Shortest Path Algorithms - Dijkstra, Floyd Warshall, Bellman Ford

➡️Section 2 Additional Practice:

Section 3: Advanced

➡️String Hashing

➡️Directed Graphs

Cycles in Directed graphs

Functional Graphs

Strongly Connected Components :

2-SAT

DP on DAGs

➡️Range Update Queries (continued)…

Additional (optional) :

➡️ Sparse Table

➡️Tree Algorithm Problems

Tree Diameter

DP on Trees

Tree Queries

➡️Section 3 Additional Practice: