---
# System prepended metadata

title: Competitive programming topics
tags: [Competitive programming]

---

# Competitive programming topics

###### tags: `Competitive programming`

# Problem theme list and tags
- Basic 
  + Calculation
  + Conditionals 
  + Loops
    + for 
    + while 
    + else, break, continue 
  + Strings
  + Arrays/Lists
  + 2D arrays
  + Functions
  + Recursive functions
- Number theory & maths
  + Number systems
    + Binary, Octal, Decimal, Hexadecimal 
    + Bitwise operations
  + Prime & composite numbers
    + Primality tests
    + Prime generation techniques
  + GCD, LCM
  + Integer Factorization
  + Count, sum, product of divisors
- Modulus arithmetic
  + Modular Inverse
  + Modulus arithmetic, basic postulates (Including modular linear equations, Continued fraction and Pell's equation)
  + Fermat's theorem
  + Euler’s Totient theorem (totient function, order, primitive roots )
  + Chinese remainder theorem  
  + Wilson theorem: nCr % p in O(p) preprocess and O(log n ) query
  + Lucas Theorem
- Math
  + Set theory
  + Inclusion-exclusion
  + Fibonacci
  + Catalan
  + Big number operations
  + Logarithmic Exponentiation
  + Josephus problem
  + Sequences
  + Polynomials
  + Matrix 
  + Probability 
  + Counting
    + Combination 
    + Permutation
    + Permutation cycles
    + Bài toán chia kẹo của Euler 
  + Burnside's lemma
  + Cayley's formula
- Computational geometry
  + Area of triangles
  + Area of polygons
  + Convex and concave polygons
  + Point inside, outside polygons
  + Center of mass
  + Overlapping rectangles
  + Line intersection
  + Circle intersection
  + Angles
  + Distances
  + Transformations: 
    + Translation (Slide)
    + Reflection (Flip)
    + Rotation (Turn)
    + Enlargement (Dilation)
  + Dot product
  + Cross product 
  + Convex hull
  + Sweep Line
- String 
  + String manipulation 
  + Search in strings
  + String prefix
  + Trie structure
  + Z-algorithm
- Prefix sum
- Data structures
  + Array/List/Vector
  + Stack/Queue
  + Linked list
  + Double linked list
  + 2D arrays, Multi-dimensional arrays
  + Map/dict
  + Set
  + Heap & priority queue
  + Hash Tables
- Searching 
  + Backtracking
  + Binary Search  
  + Ternary Search
  + Meet in the middle
- Greedy
- Sorting
  + Simple sorting 
  + Quick sort
  + Merge sort
  + O(n) sort (distribution counting)
- Recursive
  + Recursive 
  + Recursive with caching
  + Divide and Conquer
- Dynamic programming
  + 1-D DP   
  + 1-D DP with tracing  
  + 2-D DP 
  + 2-D DP with tracing
  + 3-D DP
  + Interval DP
  + Tree DP
  + Subset DP 
- Backtracking
  + Brute force
  + Backtracking with greedy paradigm
  + Backtracking with pruning
- Ad-hoc
- Suffix Array
- Graph Search
  + BFS
  + DFS 
- Graph connectivity, strongly connected components
- Eulerian Graph
- Hamiltonian Graph
- Binary tree traversal
- Reverse Polish notation: RPN
- Binary search tree: BST
- Shortest Path in a weighted Graph
- Minimum Spanning Tree
- Maximal Flow
- Maximal matching in a bipartite graph
- Game theory
- Amortized analysis
  + Two pointers
  + Sliding window
- Range queries
  + Range minimum Query(RMQ)
  + Fenwick tree (binary indexed tree)
  + Segment tree / Interval tree 
- AVL Trees
