be-oi/beoi-training

Name: beoi-training

Owner: beOI ASBL/VZW

Description: Training materials for Belgian Oympiad in Informatics

Created: 2013-02-01 12:53:14.0

Updated: 2017-11-12 12:18:41.0

Pushed: 2017-11-10 21:56:08.0

Homepage: null

Size: 37443

Language: TeX

GitHub Committers

User	Most Recent Commit	# Commits
Guillaume Derval	2016-11-19 15:11:45.0	12
Benoît Legat	2015-02-21 09:13:04.0	7
Damien Leroy	2015-02-12 15:42:38.0	4
Floris Kint	2015-04-17 11:32:57.0	18
Nico Ekkart	2016-11-19 10:56:24.0	16
Victor Lecomte	2018-02-15 17:28:05.0	117
mcouplet	2017-11-10 21:55:18.0	24
JorikJooken	2016-03-10 21:48:28.0	5
Bruno Ploumhans	2016-10-09 21:53:47.0	1
Jari Van Melckebeke	2016-07-18 08:48:02.0	2
Robin Jadoul	2017-03-20 15:05:56.0	34
Galant Damien	2017-02-19 14:05:21.0	1

Other Committers

User	Email	Most Recent Commit	# Commits
fgi-github	fgi@info.fundp.ac.be	2013-02-15 09:33:32.0	1

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.

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