Competitive Programming
Competitive Programming can sharpen one’s mind, sometimes helps with one’s interview. This post is a note of Bjarki Ágúst Guðmundsson’s Competitive Programming course.
Introduction
Quickly classify problems
- Ad Hoc
- Complete Search (Iterative/Recursive)
- Divide & Conquer
- Greedy (only the original ones)
- Dynamic Programming (only the original ones)
- Graph
- Mathematics
- String Processing
- Computational Geometry
- Some Harder Problems
Rule of Thumb
- \(10^9\) operations per second
- \(2^{10} \approx 10^3\).
Algorithm Analysis
| n | Slowest Accepted Algorithm | Example |
| \(\le 10\) | \(O(n!), O(n^6)\) | Enumerating a permutation |
| \(\le 15\) | \(O(2^n\times n^2)\) | DP TSP |
| \(\le 20\) | \(O(2^n), O(n^5)\) | DP + bitmask technique |
| \(\le 50\) | \(O(n^4)\) | DP with 3 dimensions + \(O(n)\) loop, choosing \(_nC_k=4\) |
| \(\le 10^2\) | \(O(n^3)\) | Floyd Warshall’s |
| \(\le 10^3\) | \(O(n^2)\) | Bubble/Selection/Insert sort |
| \(\le 10^5\) | \(O(nlog_2n)\) | Merge sort, building a segment tree |
| \(\le 10^6\) | \(O(n), O(log_2n), O(1)\) | Usually, contest problem have \(n<10^6\) (to read input) |
Data Structure
- Static arrays
- Dynamic arrays
- Linked lists
- Stacks
- Queues
- Priority Queues
- Sets
- Maps