Competitive programming

Hi, I am making this roadmap as a good guide to go from starting → exceptional at

competitive programming. I am not at that exceptional level, and as we go down
the list I will mention at which stage I am at. This roadmap is not based for job
interviews or just a general hobby, this roadmap is meant to progress to the
International Olympiad of Informatics and potentially ICPC (same thing but for
university students, and its teams of 3). Enjoy. The duration of each section is also
listed. Also if you do all of this you essentially get a first class in university for
computer science (I.e. an A* in computer science for uni).

First 2 weeks - Getting started with c++.

You should understand:

- Functions
- Loops
- Variables and data types
- STL (very important)
- The debugging process

Overall goal: You should start to be able to implement solutions to problems in c++. As you are
just starting, the priority is to get used to the syntax of the language and the workflow of solving
problems. Don’t focus on mastering the language, and if something comes up frequently, learn
it!
How to practice: You should be mainly doing questions on Hackerrank as they tend to be
easier and they also have a section for c++. You can also start doing problems on Codeforces
(the main cp website, but not used that much for IOI training). On codeforces, stick to
800-rated problems that have the most accepted solutions. The codeforces problems tend to
have ‘trick solutions’, by that I mean they are long and heavy-implemented problems but instead
some mathematical trick that can be solved with some basic loops and formulas.

1 Month - Basic problem solving techniques and math

You should learn:

- Algorithmic analysis (Big-O complexity)
- The Art of Problem solving Introduction to counting and probability (I will send pdf)
- The Art of Problem solving Introduction to number theory (I will send pdf) (you also need
answer booklet for both, I will send pdf)
- Complete search: searching every possible option
- Exploring the entire search space, loop conditions
- Precomputation
- Recursion
 - Iterating through all subsets (Bitmasks)
- Iterating through all permutations
- Backtracking algorithms
- Sets and maps
- Basic logic of greedy algorithms

Overall goal: Familiarise yourself with USACO bronze problems. You should understand how
to solve complete search problems, basic greedy problems and ad-hoc problems (i.e. random).
In addition, you should also try to finish both AoPS books as a strong mathematical background
is necessary in CP.
How to practice: 100% USE THE USACO GUIDE!!! This should be your number one resource
from now on and the rest of this document will loosely be based on this. USACO has excellent
problems and the guide is so helpful (I use this to practice problems). Here is a link: USACO
guide

1 ½ to 2 months - Introduction to basic algorithms

You should learn:

- AoPS intermediate Counting and probability (I will send pdf)
- Prefix sums
- Two pointer techniques (You can also learn Kadane’s algorithm, it's super simple)
- Binary search (and advanced implementations!)
- Greedy algorithms
- Priority queues & stacks
- Some string algorithms (substring matching (DO NOT LEARN KMP YET!!), palindrome
checking (DO NOT LEARN MANACHER’s YET!), etc.)
- Bitwise operations

Overall goal: Start solving problems that involve an algorithmic approach. They can increase
efficiency and make you a better CP. Also start learning the basics of bitwise operations. Prefix
sums are good at saving you runtime and binary search should always be used in monotonic
sequences. Priority queues and stacks will be helpful soon. They should still be learnt.

How to practice: Start solving USACO silver problems, and do a lot more codeforces 1000-
1500. Use codeforces, USACO problems and NEW!: AtCoder. They have more
math/algorithmic problems, but they can be really hard at IOI level.

2 - 3 months - Dynamic programming

(THIS IS ME!!!!)
These months are different, as dynamic programming is a single topic. However, it's SO
Frequent in Olympiads and SO MANY companies ask about DP problems. It’s an INCREDIBLY
USEFUL topic to understand.

You should learn:

 - Basic terminology for DP (top-down, bottom-up, tabulation, memoization)
- Classical DP problems (knapsack, grid paths, fibonacci, edit distance, LCS, LIS)
- Basic DP problem solving skills
- Bitmask DP
- 2D DP
- Whatever Dimension DP

Overall goal: You should now become comfortable approaching and solving most DP
problems. You can identify when to use DP (versus greedy) and solve problems at the USACO
gold level.

How to practice: Once again use the USACO training guide, Codeforces, atCoder. Use
leetcode to solve the classical DP problems and get used to solving them. Leetcode has more
transparent problems but I use leetcode problems when learning a new topic.

2 - 3 months - Graph theory

I apologize. I have left this out and it is really REALLY REALLY important in CP (and CS).
However I feel like it's best dedicated by itself as the amount of data structures and algorithms
are insane. Enjoy (I don’t know much about graphs yet, but I will tell you the two best resources
for learning graphs):

Resource 1: USACO guide. Graphs are covered in USACO silver, USACO gold and a bit more
in USACO platinum. Learn everything there is to know about graphs, from the very basics to the
most complex.

Resource 2: Competitive programming 4 (Steven Halim, Felix Halim). I use this book to learn
about CP concepts and their graph section is very good and very comprehensive. You can
probably find a pdf of the book online on a github repo.

Overall goal: Essentially learn all there is to learn about graphs. Representations, variations,
traversals, pathfinding, proofs etc.

Remaining:
Now that you know all the fundamentals to CP, if you have spent more time that allocated to
each section don’t worry. Now you can start to dive into more specific things such as heavy-light
decomposition, fft, centroid decomposition. Please use the USACO guide and the 2nd book to
the one mentioned in the graph section. From this point now, you should start to slowly solve
more Olympiad problems, whether it's the IOI or national olympiads. You can start doing more
practice contests and solving more problems. You have reached the stage of refinement and
are now preparing for your International olympiads. Good job!