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 👀)

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.

When you pass the sample inputs locally, click on Submit.

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 !

USACO has problems revolving around Farmer John's Farm and (mostly) His Cows.

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.

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).

Ex : mixmilk.in for input and mixmilk.out for output.
Then you need to add these lines at the start of your code:

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.

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 .

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.

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). :::

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

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!

➡️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.

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 :

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 !

## Contents :

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

- Codechef

- Topcoder

- 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)

OR

If you prefer to read, then :

OR

Register on CodeChef ; and then solve the given problems :

In the end, you truly learn the language after you have sufficient experience. Try out as many problems from these links :

## 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 CodeforcesPS : We recommend enrolling yourself in the

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 !"ITMO Academy: pilot course"More problems from CodeForcesYour first problem on CSESCSES is a problem set :register yourselfYour first problem on: Problem TESTSPOJ.com## Fast I/O (optional for now):

What it is :

Try this problem with Fast I/O :

Your First Problem on USACOAbout USACO :

(know more about it here / official page )

Or you may make your template for USACO problems like :

## Template - (Fast I/O included)

First Problem

More problems on USACO :## Basic Math Problems

## Some suggestions from the Makers :

## ➡️Time Complexity

Solve these in O(n) :

## ➡️Intro to STL

## Basic Array / Vectors Problems

## Basic String Problems

Your intro to strings : C++ Strings (With Examples)

Basic Stack Problems

## ➡️Sorting

problems :## More on STL

Continue from 35:58 : Complete C++ STL in 1 Video | Time Complexity and Notes

Basic Set / Multiset Problems

Basic Map Problems

Custom comparator

Each Data Structure in STL has its own strengths and weaknesses. Try to think what to use according to the problems.

## ➡️Binary Search

Tutorial with Visualisation

Binary Search | Code Accepted

Additional Practice## ➡️Bit Operations

Problems :## ➡️Primary Number Theory

## Binary Exponentiation

or

or

## Factorisation [till O(rootN)]

we’ll cover Sieve of Eratosthenes later*

## Gcd

More Practice## ➡️Recursion

:Basic Recursion problems## ➡️Complete Search

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

## Section 1: Basic Theory

## ➡️Number Theory

## Number Sieve

or

## Modular Multiplicative Inverse

## Additional Practice :

## ➡️Two Pointers / Sliding Windows

ProblemsAdditional problems## ➡️Range Queries

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

## Hint

search for

Kadane’s Algorithm2 D Prefix Sum## Additional Practice

## ➡️Divide and Conquer

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

## ➡️Intro to Greedy Algorithms

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

Here are some questions :

SELF ASSESSMENT:## ➡️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 .

fibonacci numbers, then try this problem :DP on Grids :This tutorial has some generic problems which will develop your understanding about grids .

DP Bitmask :Some Problems :`DP is a topic which can be mastered only through practice.`

SELF-ASSESSMENT ( Topic : DP )Some Question on Dp + Probability and expected values :## ➡️Interactive Problems

Here is a tutorial on how to solve interactive problems .

## Here are some questions :

Some more tools to help you in your journey :

CodeForces Chrome Extensions :

## ➡️Section 1 Additional Practice:

## Section 2: Intermediate

## ➡️Advanced Maths

CombinatoricsMatricesProbabilityExtra Number Theory## ➡️Range Update Queries

## ➡️Graph Theory Basics

## BFS and DFS

## Cycles Detection

## Bridges in Graphs

## Flood Fill

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

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

## Subtree/DFS Problems

## ➡️DSU + MST

## Disjoint Set Union

## Minimum Spanning Trees

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

## ➡️Section 2 Additional Practice:

Optional :

## Section 3: Advanced

## ➡️String Hashing

## ➡️Directed Graphs

## Cycles in Directed graphs

## Functional Graphs

Cycle Finding :In Kahn's Algorithm : If all nodes in the graph are not removed as zero degree -> it implies that there must be cycles.

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

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.## 2-SAT

## DP on DAGs

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

## ➡️Range Update Queries (continued)…

This topic is continued from the previous section.

## Additional (optional) :

## ➡️ Sparse Table

## ➡️Tree Algorithm Problems

## Tree Diameter

## DP on Trees

(this section builds on from DP on DAGs)

## Tree Queries

## ➡️Section 3 Additional Practice:

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

Blogs-✧

YouTube Channels and Playlists-This roadmap could never be possible without the inspiration and background support of the

Makers of the Previous Roadmap:Contributors-Tattwa Shiwani | tattwash23@iitk.ac.in

Khushi Ranawat | rkhushi23@iitk.ac.in

Arnav Gupta | arnavgupta23@iitk.ac.in

Yatharth Dangi | yatharth23@iitk.ac.in

Rohit Somani | rohitvs23@iitk.ac.in