List of topics in Competitive Programming

printf, scanf
- printf scanf %d, %f, %lld, %c %s
- printf %.6f, %02d
- scanf space %c
- %[^\n], gets
- cin, cout

variables
- int, long long, range
- type casting
- integer division floor, ceil +mod-1
- operator casting (int/int = int, int*int = int)- const, #define

operators
- +-*/%
- +=, -=, *=, /=, %=
- ternary operator ?:
- prefix/postfix ++/--
- modulo operator (negative value)
- modulo add/multiplication

bitwise
- &, |, ^, >>, <<, ~
- >>=, <<=

if-else
- if, else, else if
- logical operator &&, ||, !
- bool (true != 0, false == 0)
- bool comparison (== xnor, != xor)

loop
- while, do-while, for loop
- infinite loop while(1) while(true) for(;;)
- nested loop

array
- base 1 index
- n-dimensional array
- cnt++
- counting/boolean array

pointer
- pointer to one variable
- pointer to array
- dynamic memory allocation (variable, array)
- array to pointer degeneracy

functions
- void function
- return function
- pass by value (copy), pass by address
- pass by reference (c++)
- return via address argument
- return by pointer, malloc
- #define, inline

recursive function
- void function
- return function
- print before recur (tail recursion)
- recur before print (head recursion)
- multiple recursion (divide & conquer/brute force)
- induction (recursive mechanism)

struct/class
- normal struct
- nested struct
- array in struct
- struct in array
- pointer to struct
- operator overloading (<)
- functions inside struct (class methods)
- comparator class
- constructor
- passing struct into function, returning struct

linked list
- push_front, push_back, insert at position, delete at position, delete value, insert sorted
- print, print backward, free list, search (return bool, int, node*)
- doubly, circular, circular doubly, xor linked list (idea only)
- STL list

string
- char array, \0
- strlen, strcpy, strncpy, strcat, strncat, etc.
- STL string
- string problem
  - palindrome checking
- string searching
  - KMP, rabin-karp (hashing)
- suffix tree
- suffix array, lcp array, lcp-lr array
- suffix automaton (aho-corasick)

sorting
- select/bubble/insert
- counting sort
- sorting pair/struct
- STL sort
  - compare function
  - lambda function
- merge sort
- quicksort
  - how to pick pivot (random, leftmost, median of three, median of medians)
  - partition (2 styles: lomuto, ___)
  - quickselect
- radix sort
  - decimal system
  - bitwise (binary/hexadecimal system)
- heap sort

graph
- graph
  - definition
  - directed, undirected
  - weighted, unweighted
- graph representation
  - adjacency matrix
  - adjacency list
  - edge list
  - using pair to store edge data with weight
- dfs/bfs on graph
  - check cycle
  - component counting
  - bipartite graph
  - shortest path
- shortest path algorithm
  - dijkstra's algorithm
  - bellman-ford
  - floydW
  - shortest path faster algorithm
- modelling state graph (implicit graph)
- minimum spanning tree
  - min sum, max sum, min max edge, max min edge
  - number of MST
  - kruskal's/prim's algo
- topological sort
- articulation point/bridge/scc

flow algorithm
- max flow algorithm
  - edmond karp
  - dinic
  - push-relabel
- min-cut max-flow theorem
- reducing vertex cover on bipartite graph to max flow
- min-cost max flow algorithm

tree
- binary tree
  - node type: root, leaf, internal node
  - complete binary tree
  - LCA
- preorder/postorder/inorder traversal
- expression tree (shunting-yard algorithm)
- heavy light decomposition
- centroid decomposition
- dp
- dsu on tree (sack), merge small to large trick

brute force
- iterative (loop)
- recursive pick/unpick, more choices
- recursive backtracking (nqueen, sudoku, permutation)
- simulation problem
- A*, branch and bound (heuristics)
- state search (graph)
- np-complete, fixed parameter

divide and conquer
- max sum subarray
- closest pair of point
- skyline
- binary search
  - transforming optimization to decision
  - binary search bound (l, r, mid+1?)
  - std lower_bound, upper_bound
- ternary search
  - search for bitonic cutting point
- modular exponentiation
- divide and conquer optimization
- centroid decomposition

dynamic programming
- optimal substructure
- overlapping subproblems
- difference between d&c and dp
- dp direction/manner (prefix/suffix)
- top-down/bottom-up
- type of DP (ultimate TOI Guide)
- classic problem
  - fibonacci
  - max sum subarray
  - longest increasing subsequence
  - longest common subsequence
  - edit distance
  - knapsack, subset sum
  - substring dp (optimal BST, matrix chain)
  - pascal triangle
  - largest 1 subsquare in a matrix
- matrix exponentiation
- dp optimization
  - convex hull optimization
  - divide and conquer optimization
  - knuth optimization

game theory
- minimax algorithm
  - alpha-beta pruning
- grundy number, xor
- nim game

greedy algorithm
- sorting criteria
- exchange argument (proof by bubble sort)
- classic problem
  - activity selection
  - fractional knapsack

data structure
- stack, queue, deque
- binary heap (priority queue)
- binary search tree
  - balanced BST (avl, rb, treap, splay)
  - treap: implicit treap, merge, split
  - application: interval tree, k-d tree, etc.
  - order-statistics
- STL set, map
- hash table
- segment/fenwick tree
  - lazy propagation
  - set on segment tree
  - dp on segment tree
- union-find disjoint set (dsu)
- persistency
- sqrt decomposition
- time segment tree, persistency trick
- sparse table

techniques
- sliding window algorithm
- binary exponentiation
- prefix sum/difference array
  - +1 front, -1 back
- line sweep algorithm
- coordinate compression
- sqrt optimization
- mo's algorithm
- parallel binary search
- meet in the middle
- 2SAT

complexity analysis
- simple analysis
- master's theorem
- amortized analysis
  - aggegrate method
  - accounting method
  - potential method

math techniques
- gcd, lcm, sieve
- (extended) euclidean algorithm
- diophantine equation
- prime number finding/checking (sqrt)
- prime factorization
- time comp. proof using harmonic series (1 + 1/2 + 1/3 + ...)
- modular inverse
- combinatorics (star and bar, inclusion-exclusion, pigeonhole)

linear algebra
- rotation matrix
- basis of vectors/cycles (graph)
- gaussian elimination
- matrix multiplication
- fast fourier transform

geometry
- convex hull
- farthest pair of point
- line intersection
- point in polygon
- orientation

computational theory
- finite automata
- grammar