search

be-oi / beoi-training

Public training materials for Belgian Oympiad in Informatics
30 stars 13 forks source link

readme

beOI/beCP Training Resources

This repository hosts all the course materials created for the beOI (Belgian Olympiad in Informatics) and beCP (Belgian Competitive Programming) training camps. Remember though that You don't need advanced topics for bronze and maybe even for silver (Bruno Ploumhans, 2018, Line 21).

The program is now structured into a set of teaching units, designed to cover the whole IOI syllabus (and some additional material from the CP3 book). Each unit contains the slides used and a README which outlines the content of the unit, lists the prerequisites and gives links to related exercises. The units are not originally meant to be in a logical order.

The resources made prior to the units system are available in the archive directory.

Teaching units

Here is the list of completed and planned teaching units. As they are still under construction, the units might not contain all the topics mentioned in the parentheses.

  1. Algorithms and complexity (big oh, practical limits)
  2. Linear data structures (array, bitset, vector, linked list, stack, queue)
  3. Sorting algorithms (selection, insertion, merge, quick)
  4. Tree data structures (set, map, heap)
  5. Balanced binary search tree (treap, red-black, order statistics with library)
  6. Graph basics and representation (adjacency matrix, adjacency list)
  7. Union-find structure
  8. Segment tree (regular, lazy)
  9. Fenwick tree (binary indexing, least significant bit)
  10. Recursive backtracking (pruning, bitmasks)
  11. Binary search (nontrivial applications, binary search the answer)
  12. Greedy (basic idea, coin change, load balancing, interval scheduling)
  13. Dynamic programming I (top-down, bottom-up, classical problems)
  14. Graph traversal (DFS, BFS, toposort, bipartite check, Kosaraju SCC)
  15. Specialized DFS (cycle check, articulation point, bridge, Tarjan SCC)
  16. Minimum spanning tree (Kruskal, Prim, variants, minimax/maximin path)
  17. Single-source shortest path (review BFS, Dijkstra, Bellman-Ford)
  18. All-pairs shortest path (Floyd-Warshall, applications)
  19. Network flow (Edmonds-Karp, min cut, vertex capacity, vertex/edge-disjoint paths, MCMF)
  20. Directed acyclic graph (longest/shortest/counting paths, tree MVC)
  21. Eulerian path (eulerian check, finding the path/cycle, Chinese postman problem)
  22. Bipartite graph and MCBM (augmenting path algorithm, MIS, MVC, min path cover on DAG)
  23. Miscellaneous math (fast pow, Fibonacci, powers of adjacency matrix, tortoise and hare)
  24. Number theory (GCD, prime factors, sieve, extended Euclid)
  25. Game theory (subtraction/Nim game, minimax, alpha-beta)
  26. String processing (trie, Rabin-Karp, Z-algorithm, KMP)
  27. Computational geometry (basics, polygon area, convex hull)
  28. Advanced search techniques (heavy pruning, meet in the middle, A*)
  29. Dynamic programming II (bitmask, drop one parameter, bitonic TSP, sliding window)
  30. Problem decomposition
  31. Advanced graph problems (2-SAT, MWIS (tree, bipartite))
  32. Sparse table, lowest common ancestor