# I) What is competitive programming?

A competitive programming contest is a place where you write code to solve the problem in the contest. Let’s say you encounter the problem:

Given 2 numbers A and B. Calculate the area of the rectangle formed by 2 sides with length corresponds to A and B.

Well, one could easily finds out that the result = A * B. So we can write C++ code:

#include <iostream>

using namespace std;

int main() {

int A, B;

cin >> A >> B;

int result = A * B;

cout << result << endl;

}

After writing the code, we submit it onto the judge, then the judge will test your code using hundreds of test cases. There are 2 types of contest:

- OI (Olympiad in Informatics): if your code passed 50% test cases, then you will receive 50% the score of the problem. The reason why people refer this scoring system as OI is because the biggest contest for the High School Students for competitive programming – the International Olympiad in Informatics (IOI) – uses this method.
- ACM (Association of Computing Machinery): only when your code passed 100% the test cases, you will receive 100% score for the problem, else you get 0 point. This grading system is used in the ACM ICPC – the contest for the University Students working in group of 3 to solve from 10 – 12 problems for 5 hours straight.

# II) Why should you do competitive programming?

**Fun**: By exploring different aspects of Math, or various techniques to optimize the code’s performance, sometimes you might end up feeling satisfy from your achievements.**Money**and**Fame**: Yes, sometimes (well in Vietnam it is everytime) you get high rank in the contest, you receive money and fame as the reward.**Intelligence**and**Wisdom**: To be honest, when I was a kid I had never try to learn math and stuffs, because back then I always get grade 10 without even trying to (too easy wtf?). However when I grow older, math gets hard very quick. I even got a 4/10 in the entrance examination of my High School (yeah, i suck!). However, my thinking is pretty quick now after training competitive programming for 2 – 3 years.**Career**: having high rank or certificates is a good proof that you are a good programmer with high skill and smart. This can lands you good places in the Computer career like the Software Engineer (Backend + Frontend), DevOps, Security Specialist, … (you can refer to here)

# III) How to get good in competitive programming?

The only way is to learn, learn and learn!

However, I can give you some guidance which helps you learn faster:

## 1) Different sites for you to start exploring:

- Codeforces: #1 alot of different categories + weekly 2h contest for you to improve yourself
- Hackerrank
- UVA
- Codechef
- A2oj: A whole bunch of different categories which is even more compare to Codeforces

## 2) Road map

#### a) Beginner:

_ Good understanding in your primary language, here I prefer using C++. In that case: know cin, cout, printf, scanf, if, else, for, while, break, continue, writing function, recursive function, vector

_ Know how to calculate **Complexity**.

_ **Dynamic Programming** level 0: know how to create your own function and solve problem using that function (I will cover this in another part)

_ **Binary Search** and **Ternary Search**

_ **Sort** Algorithms: Insertion Sort, Bubble Sort, Shell Sort, Heap Sort, Merge Sort, Quick Sort, …

_ For **math**-like problems:

+ Understands bit operator

+ Greatest Common Divisor

+ Sieve Eratosthenes

+ Count number of divisor of a given number N in O(√N) (also verify if it is prime number)

+ Prime Factorization a given number N in O(log(n)) and O(√n)

_ For **String** problems:

+ Understands char and int conversion

+ KMP

+ Z_Function

_ **Graph** theories:

+ Bridge, Vertex Seperator

+ BFS and DFS

+ Tree + finding diameter of a tree

+ Topology sort of Directed Graph

### b) Intermediate:

Wow, if you have known and solved problems that consist of the above knowledge, congratulation in joining the Intermediate group.

_ **Data Structure**:

+ Heap (using priority_queue or “set” in C++)

+ Interval Tree (+ lazy propagation)

+ Range Minimum Query (RMQ)

+ RMQ on Tree and Lowest Common Ancestor (LCA)

+ Binary Indexed Tree (BIT) or also known as Fenwick Tree

_ **Dynamic Programming** level 1:

+ Bitmask

+ DP in Combinatorics

_ For **math**-like problems:

+ Probability

+ Expected Number

+ Combinatorics

_ For **String** problem: To be honest, I think the difficulty of String for Beginner is somewhere between the Beginner and Intermediate, so here is just the same like Beginner.

_ **Graph** theories:

+ Dijkstra (using Heap)

+ Bellman Ford

+ Kruskal (+ Disjoint Set) and Prim

+ DP on Tree

### c) And so on:

After you have conquer all the knowledge above, it is time for you to go find new challenge. Below is some techniques that I have discovered:

_ **Array**-like:

_ Mo’s Algorithm

_ Persistent Tree

_ Splay Tree

_ **Geometry**:

+ 2D Geometry: Point, Line, finding intersection of Lines, Polygon, finding Convex Hull, Circle, Circle intersecting with lines, etc

+ 3D Geometry: solving problems like 2D geometry

+ KD Tree

_ **Optimizing Dynamic Programming**:

+ Convex Hull Trick

+ Divide and Conquer

+ Knuth Optimization

All 3 is in here

_ **Math**-like:

+ Game theories: Xor Nim + Grundy

+ Matrix Multiplication

+ Extended Euclid

+ Chinese Remainder

+ Integral and Derivative

+ Crazy-ass function-like problems

_ **Strings**:

+ Suffix Array and LCP

+ Ahocorasick

_ **Graphs**:

+ Heavy Light Decomposition

+ Centroid Decomposition

+ Link cut Tree

+ Bidirectional

_ **Flow**:

+ Max flow min cut

+ Max flow min cost

# IV) Conclusion:

This road map was written by me – a competitive programmer who has been studying for about 4 – 5 years and won various competition in the Olympiad in Informatics as well as ACM ICPC.

# Thank you for reading. Hope you find your passion in this field. Enjoy!