Roadmap to
Competitive Programming (CP)
INTRODUCTION:
➡️What is CP?
I t's a mind-sport where you are given a problem and have to develop optimised
solutions for the given constraints with your coding skills. This helps us in
building our logical and analytical thinking skills and also in enhancing our
knowledge.
Now, the question is how we can do Competitive Programming.
➡️Various CP Platforms (Online Judge)
✧ An online judge is an online system to test programs in programming contests.
It runs the code for test cases which are hidden and compares it with the
expected output within the memory and time limits imposed.
✧ Some Popular CP Platforms are -
Codeforces(We will see more about it further…),Codechef,Atcoder,Topcoder,
Hackerrank,Leetcodeetc.
✧ Some Popular Coding Cups / Hackathons -
➢ International Collegiate Programming Contest (ICPC) - Oldest, largest
and most prestigious programming contest in the world.
➢ Hacker Cup - FacebookMeta’s annual open programmingcompetition.
➢ ICFP - A three-day open programming competition.
GETTING STARTED:
\
W hat’s better than some advice from the bestto get started?
● How to start Competitive Programming? For beginners!
● How To Become Red Coder? (codeforces.com)
➡️Pre-Requisites -
W hat text editor or IDE should I use for competitive programming?
ome of you may have thought about which editor to be used for competitive
S
programming. Well, some of the good editors for CP are Sublime Text (for both Linux
and Windows), CodeBlocks (for Windows only), and Geany. However, if someone still
uses online editors (GeeksForGeeks, Codeforces, Ideone, or CodeChef IDE), switch to
offline editors as soon as possible. Online editors should not be used during the contests
because the site may crash at that time, and you may lose the unsaved code. Also, if you
are using Ideone or Pastebin, your code may get stolen, and you might be caught in
plagiarism.
ow talking about the offline editors, if you have Linux installed on your laptop, you
N
can easily set up Sublime Text on it. (InstallingSublime Text on Linux,Set Up Sublime
Text in Linux). However, if you are using Windows,try setting up Sublime Text
(S
ublime Text for Windows). However, if it is givingany errors which you are not ableto
resolve, then you can set up CodeBlocks easily on your system. You can also set up
Geany on your Linux system if you want.
( Linux setup for Competitive Programming (with Geany) )
➡️Week I -
✧ So, in the first week, we will start with the most essential things required for
CP, which areLearning a LanguageandUnderstandingTime and Space
omplexity.
C
✧ On the language part, we would be learning C++ because it’s the most
commonly used language in CP for two main reasons:a.It’sfaster than any other
p rogramming languagein terms of speed,andb.Ithas a veryvast Standard Template
Library(which we are going to cover in the upcomingweeks)
✧BREAKDOWN -
Day I n Day-I, we will be covering the sheer basics of C++,
O
including theBasic Syntax, I/O and Variables.
Introduction to C++ -
- Basic Syntax and Structure
- Input/Output in C++
- Comments in C++
Variables and Data Types -
- Variables and Literals
- Fundamental Data Types in C++
- Typecasting in C++
- Scope of a Variable
- Operators in C++
Day II oving on to Day-II we would be covering theFlow
M
Control in C++.
Now, what is Flow Control?
Flow control statements serve to specify what has to be
done by our program, when, and under which
circumstances. It includes Conditional Statements and
Loops.
Conditionals in C++ -
- If-Else Statements
- Switch-Case Statements
- Ternary Operator(Substitute for if-else)
Loops in C++ -
- W hile and do-While Loops
- For Loop
- BreakandContinuestatements
Day III oving on to Day-III we would be covering the most
M
fundamental kind of data structure in C++ which is an
Array. We will also cover the implementation ofStrings
(both C-Style and string Object).
We would also introduce you toPointers and
Dereferencing.
Arrays in C++ -
- Introduction to Arrays
- Multidimensional Arrays
Strings in C++ -
- C-Style and C++-Style Strings
- More with string Object in C++
Pointers and Dereferencing -
- Introduction to Pointers
- Working with Pointers in Arrays
- Dynamic Memory Allocation in C++
Practice Time !!
- R everse words in a given string
- https://codeforces.com/problemset/problem/1760/B
- https://codeforces.com/problemset/problem/1703/C
- https://codeforces.com/problemset/problem/1758/A
Day IV oving on to Day-IV we would be wrapping up the
M
things in C++. Today, we will be dealing withFunctionsin
C++andRecursion.
Functions in C++ -
- How to create Functions?
- Default Arguments in a Function
- Passing Array to a Function in C++
- Call by Value v/s Call by Reference
Recursion -
- Introduction to Recursion in C++
- Recursion and Backtracking
Practice Time !!
- h ttps://www.codechef.com/problems/FIBXOR01
- https://www.geeksforgeeks.org/partition-set-k-subsets-equ
al-sum/
- https://www.geeksforgeeks.org/given-a-string-print-all-pos
sible-palindromic-partition/
Day V I t's time we move on to the various coding platforms like
Codeforces, Codechef etc. Of these,Codeforcesisthe
main, so we have adetailed overviewfor you of thejudge.
or other Judges, the UI is straightforward, and a
F
breakdown of the rating system is provided below.
- CodeChef
- AtCoder
- HackerRank
- TopCoder
I t is advised to spend some time on these platforms and
familiarise oneself so that one is comfortable with these
platforms, as these will be a constant part of the CP
Journey.
Day VI n Day-VI, we will discuss the Big-O Notation and its
O
relation to the CP scenario. We will get an overview of the
classification and an overview of how to judge the time
complexity of an intended solution using the constraints
of a problem.
- Introduction to Time Complexity
- Big O Notation
- Judging Constraints
Practice Time !!
- As an exercise, you can analyse the time complexity
of the problems you have solved till now and figure
out the bound of the algorithm used using the
Big-O Notation.
- Trick questions from Time & Space Complexity -
Coding Ninjas CodeStudio
Day VII ractise day?Check out the resources given below,like
P
ladders etc.
You guys can now do lower-rated Codeforces problems
(<1300) on A2OJ Ladders and Introductory Problemson
CSES Problem Set…
2OJ Ladders
A
CSES Problem Set - Tasks
Solve C++ | HackerRank
✧ Some Extra Topics for Week I - (Depends on your interest :)
- Structs in C/C++
- Linked List and its Implementation
- Object Oriented Programming (OOPS) in C++
- Common Errors in C++
➡️Week II -
✧ We are going to coverC++’s Standard Template Libraryor STL in the upcoming
two weeks (Week II and III).
✧ W hat is STL?
TL contains a lot of predefined functions and data structures that can be used in CP.
S
So it becomes important for us to learn STL to improve CP.
✧ You can go through thislinkto get an overviewof STL.
✧ Since STL has a lot of functions and predefineddata structures in STL, it can be
verwhelming to go through every one of them. So we will be covering only some of the
o
most useful data structures in STL that you are most likely to encounter during your CP
journey.
✧ BREAKDOWN -
Day I I terators -
They are very similar to pointers in various ways, it might
be a little tricky to fully understand without any prior
knowledge of STL containers.
But try to read about them from thisblog.
To iterate over Different containers using aRange-based
for loop in C++ provides a sleek syntax.
Day II-III Sort -
Here is a link to learn about sort in C++ -Sort
ambda expression -
L
You can read about it fromLambda expression in C++-
GeeksforGeeks.
These are useful when you want to write custom
comparator functions.
Practice Time !!
- ttps://codeforces.com/contest/903/problem/C
h
- Ferris Wheel
- Musical Rods - Problems | CodeChef
- https://codeforces.com/problemset/problem/492/B
- https://codeforces.com/problemset/problem/1545/A
air -
P
Pair is a relatively simple container, defined in STL, it is
used when we want to store two data together.
Give it a read from thisblog.
Practice Time !!
- The Monk and Class Marks | Practice Problems
Day IV Vectors -
ector is a C++ container that is used to store a particular
V
data type. They are very similar to the classical array but
have a lot of advantages over them.
For more on vector v/s arrays, you can go through the
Advantages of a vector over an array in C++.
Now give a read to the vectors part of thisblog.
Practice Time !!
- M aximize the sum | Practice Problems
- Minimum operations | Practice Problems
- Infinite arrays | Practice Problems
Day V Binary Search, Lower Bound & Upper Bound -
inary search is a searching algorithm in a sorted array
B
that exploits the sorted nature of the array and reduces
the time complexity to O(log n).
Lower bound and upper bound are functions that use
binary search in their implementation. You can see the
applications in the following articles:
- Binary Search - Algorithms for Competitive
Programming
- std::upper_bound and std::lower_bound for Vector
in C++ STL - GeeksforGeeks
Practice Time !!
- h ttps://codeforces.com/problemset/problem/1566/A
- https://codeforces.com/group/ctEtdi2TSJ/contest/396408/p
roblem/A
- https://codeforces.com/group/ctEtdi2TSJ/contest/396408/p
roblem/E
- https://codeforces.com/contest/1370/problem/D
Day VI tacks -
S
Stacks are a type of container with LIFO (Last in First
Out ) type of work, where a new element is added at one
end (top) and an element is removed from that end only.
You can refer to thisarticleto learn about syntaxand
basic functionalities in the stack.
Practice Time !!
- P arenthesis Checker | Practice | GeeksforGeeks
- https://practice.geeksforgeeks.org/problems/next-larger-el
ement-1587115620/1?page=1&category[]=Stack&sortBy=sub
missions
- Longest valid Parentheses | Practice | GeeksforGeeks
Day VII Practice Time !!
- h ttps://codeforces.com/problemset/problem/1183/D
- https://www.geeksforgeeks.org/the-stock-span-problem/
- https://codeforces.com/group/ctEtdi2TSJ/contest/384123/p
roblem/H
- https://codeforces.com/group/ctEtdi2TSJ/contest/396408/p
roblem/E
- https://codeforces.com/problemset/problem/1201/C
➡️Week III -
✧ BREAKDOWN -
Day I ueue -
Q
Queue is a type of container adapter that operates in a first in
first out (FIFO) type of arrangement.
More about the queuehereand in thisblog.
Practice Time !!
- F irst negative integer in every window of size k | Practice |
GeeksforGeeks
- Disk tower | Practice Problems
Day II - III Map, Unordered-map, Multimap, Unordered_multimap -
ou can go through different map operations in thisblog.
Y
Map-Map in C++ Standard Template Library (STL) -
GeeksforGeeks
Unordered_map -unordered_map in C++ STL -
GeeksforGeeks
Multimap - Multimap in C++ Standard Template Library
(STL) - GeeksforGeeks
Unordered_Multimap - unordered_multimap and its
application - GeeksforGeeks
Practice Time !!
- ttps://codeforces.com/contest/4/problem/C
h
- Subarray with 0 sum | Practice | GeeksforGeeks
- Sum of Two Values
- CSES - Subarray Sums I
Day IV- V Sets, Unordered_set, Multiset, Unordered_Multiset -
et -Set in C++ Standard Template Library (STL) -
S
GeeksforGeeks
nordered_set -Unordered Sets in C++ Standard Template
U
Library - GeeksforGeeks
ultiset -Multiset in C++ Standard Template Library(STL)
M
- GeeksforGeeks
nordered_multiset -Unordered_multiset and its uses-
U
GeeksforGeeks
Practice Time !!
- wice Counter | Practice | GeeksforGeeks
T
- https://codeforces.com/contest/855/problem/A
- https://atcoder.jp/contests/arc087/tasks/arc087_a?lang=en
- Monk and the Magical Candy Bags | Practice Problems
- https://www.geeksforgeeks.org/largest-subset-of-array-having
-sum-at-least-0/
Day VI riority Queue -
P
Priority queues are containers similar to queue, but the only
difference is that the top element is always the maximum of
the set.
Priority queues are implemented internally using binary
search tree. So insertion and deletion are O(log n).
Read more about priority queues in thisblog.
Practice Time !!
- M onk and the Magical Candy Bags | Practice Problems
- K-th Largest Sum Contiguous Subarray | Practice |
GeeksforGeeks
Day VII emember, When in doubt, always refer to:
R
Cppreference.com
ow you can create a Template code for yourself
N
But wait,
W hat are template codes? How Should I create one for
myself?
Templates are some pre-written code that competitive
programmers use to make their Coding faster and more
efficient.
For example, take thisSample Template
o understand this Template better, you can go through this
T
doc.
ow, that you know a lot of stuff so you are a lot more likely
N
to make a lot of mistakes so here is a video that would be of
great help
C++ Mistakes Noobs Make (and how to prevent them)
y now you are well familiar with C++ STL, so you will be
B
better able to appreciate this blog and use it:C++tips and
tricks - Codeforces.
➡️Week IV -
✧
So, in the fourth week, we will be covering some miscellaneous topics that are
very much essential as you proceed higher up in the domain of Competitive
Programming.
✧ The topics include - Prefix Sums, Number Theory, Dynamic Programming
and Bit Masking.
✧ This section is more about practice, the content would be very minimal, but you
can improve your grip on these topics by practising more and more…
✧BREAKDOWN -
Day I Prefix Sums -
- Prefix Sums
Practice Time !!
- roblem 2. Hoof, Paper, Scissors
P
- Power of Points
- Forest Queries
- Problem 2. Subsequences Summing to Sevens
Day II Number Theory -
- Number Theory
- Sieve of Eratosthenes - GeeksforGeeks(useful for
finding primes quickly in a range)
- M
odular Inverse - Algorithms for Competitive
Programming
Practice Time !!
- SES - Exponentiation II
C
- CSES - Counting Divisors
- CSES - Sum of Divisors
- https://codeforces.com/contest/1349/problem/A
- https://codeforces.com/contest/1758/problem/D
- https://codeforces.com/contest/1811/problem/D
Day III Bit Masking -
- Bit Manipulation
- CF Blog - Bitmasks for beginners
Practice Time !!
ry implementing addition and multiplication using bitwise
T
operators only (you can use
loops)https://codeforces.com/problemset/problem/1514/B
- https://codeforces.com/problemset/problem/1615/B
- https://codeforces.com/contest/1758/problem/B
- Counting Bits
- Maximum Xor Subarray
- https://codeforces.com/contest/1207/problem/E
- https://codeforces.com/contest/276/problem/D
- https://codeforces.com/problemset/problem/1614/C
Day IV - V Dynamic Programming -
- DP - From Novice to Advanced
- More Resources for DP
Practice Time !!
I t is an excellent idea to solve the entireCSES‘dynamic
programming’ section (except the last 2-3 questions).
Some selected problems are given below:
- Coin Combinations I
- Coin Combinations II(contrast with the previous problem)
- Two Sets II
- https://codeforces.com/problemset/problem/455/A
- Longest Common Subsequence - LeetCode
- CSES - Projects
Sliding Window -
Day VI - Sliding Window Technique
Practice Time !!
- h ttps://codeforces.com/problemset/problem/279/B
- https://cses.fi/problemset/task/1077
- https://cses.fi/problemset/task/1076
DA YVII Practice Time !!
Here are some questions for your practice:
- ttps://codeforces.com/problemset/problem/1234/C
h
- https://codeforces.com/contest/1557/problem/B
- Problem 1. Sleepy Cow Herding
- https://codeforces.com/contest/1529/problem/B
➡️Week V -
✧
So, in the five week, we will be covering some advanced data structures topics
that are very much essential as you proceed higher up in the domain of
Competitive Programming.
✧ The topics include - Basic Graph Theory, Trees and Segment Trees.
✧ This section is more about learning , there week will be containing heavy
learning, but you can improve your grip on these topics by practising more and
more…
✧BREAKDOWN -
Day I Introduction to graphs -
- https://www.geeksforgeeks.org/graph-types-and-a
pplications/
- https://www.youtube.com/watch?v=gX EDmodO
J&t=899s&ab_channel=mycodeschool
- Difference between Graph and Trees
Day II I mplementation of graphs-
Firstly, we will be looking at the implementation of graphs
in C++.
- Graph Representation
- Graph Representation Video
Practice Time !!
- h ttps://codeforces.com/problemset/problem/292/B
- https://codeforces.com/problemset/problem/1829/F
Day III-IV raph Traversal Algorithms-
G
Now we are going to learn how to traverse through a
graph.
Breadth First Search -
- Lecture on BFS
- Cp Algorithms
Day V Depth First Search -
- Lecture on DFS
- Cp Algorithms
I f you are still struggling to get an intuition for these
algorithms you can check these resources might help you.
- W illiam Fiset
- Reducible
Practice Time !!
- ttps://atcoder.jp/contests/abc315/tasks/abc315_e
h
- https://codeforces.com/problemset/problem/1843/D
- https://codeforces.com/problemset/problem/1830/A
- https://codeforces.com/problemset/problem/1143/C
DA YVII Segment Tree-
his is a relatively hard data structure for beginners. This data
T
structure is required generally for problems of rating >= 1800.
- Course by ITMO University
- Cp Algorithms Segment Tree
ote : Only Cover the starting portions of the Cp Algorithms
N
Segment Tree Section.
Do try the questions given in the ITMO University course as they
contain all the standard uses of Segment Tree.
Practice Time !!
hese are some of the easy questions from the practice problems
T
section of cp algorithms.
- https://codeforces.com/problemset/problem/339/D
- h ttps://codeforces.com/problemset/problem/1234/D
- https://codeforces.com/contest/356/problem/A
- https://cses.fi/problemset/task/1735
➡️Some More Resources -
✧ Books -
● Competitive Programmer’s Handbook | CSES
● Guide to Competitive Programming | Springer
✧ Problem Sets and Resources -
● CSES Problem Set
● A2OJ Ladders
CP-Algorithms
●
✧
Blogs -
● Blog: From Rating 1000 to 2400+
● Blog: From Rating 1000 to 2000
75LeetCode Questions to save your time
●
✧
YouTube Channels -
● Errichto Algorithms-He has educational videos ofvarious useful topics like
dynamic programming, binary exponentiation and other useful topics.
● William Lin-He has done a live stream of the fullcses problem set which some
f you might find helpful. He also has screencasts of various codeforces and
o
codechef rounds.
✧ Miscellaneous-.
● Video about how to debug your code efficiently
● Codeforces Blog on Debugging
✧ Websites and Extensions-
● AtCoder Problems-This site contains a collectionof all the problems on
atcoder according to their rating. Similar to A2OJ Ladder.
● Contest Mania-This site might be helpful when youare trying to find a contest
t hat you didn’t solve so that you can give it as a virtual contest. Just login your cf
id on the bottom left corner.
● Carrot-This extension contains everything like whatwas your actual
erformance in the contest, how many rating points you will gain after the
p
contest, etc.
● CF Analytics-This extension displays the number of problems solved per rating
a nd links to unsolved problems.This also shows number of problems solved per
topic as well.
Contributors -
● Sanat Goel | 9779589799
● Vipul Chanchlani | 9462150839
● Goutam Das | 9827708951
● Rishi Agarwal | 7071377085
● Varun Tokas | 9990825216
● Shivam Mishra | 8604397668
● Chayan Kumawat | 9569426190
● Prerak Agarwal | 8528203343
● Sankul | 9315719561
