Road to become a competitive programmer

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:

  1. 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.
  2. 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?

  1. 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.
  2. 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.
  3. 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.
  4. 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:

  1. Codeforces: #1 alot of different categories + weekly 2h contest for you to improve yourself
  2. Hackerrank
  3. UVA
  4. Codechef
  5. 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

Hash algorithm

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!

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s