Competitive Programming (CC3032) | |

Pedro Ribeiro - DCC/FCUP |

| Evaluation | Lists and Rankings | Classes | Online Judges | Study Material | Other Similar Courses |

Slack (register) *"instant messaging"* questions and answers

Evaluation

- Evaluation Formula (see the preliminary final grades)
**Weekly Problems**- #00 - Introduction to the course and the online judges
*(not counting to grade)* - #01 - Sublinear complexity data structures (map, set, priority_queue)
- #02 - Sorting, binary search, ternary search, bisection
- #03 - Sqrt decomposition, segment trees and variants
- #04 - Cumulative sums and fenwick trees (BITs)
- #05 - Dynamic Programming I (classic)
- #06 - Dynamic Programming II (partitions, games, dags, counting, search)
- #07 - Graphs I (DFS, BFS, topological sorting, articulation points, bridges, euler paths, ssc)
- #08 - Graphs II (distances: dijkstra, bellman-ford, floyd; MST: prim+kruskall; max flow)
- #09 - Strings (KMP, Aho-Corasick, tries, suffix trees, suffix arrays)
- #10 - Computational Geometry (points, lines, polygons, intersections, areas, inclusion, convex hull)

- #00 - Introduction to the course and the online judges
**Competitive Events**

- 1st Contest:
**8 jan, 12:00-13:40**, online AtCoder Beginner Contest (AtCoderBC) (if needed, I will count best live AtCoderBC in [1 dec - 31 jan]) - 2nd Contest:
**12 jan, 14:00-17:00***(in class, partial points per problem)* - 3rd Contest:
**23 feb, 14:00-18:00***(final contest, individual or groups of 2)*

- 1st Contest:

Lists and Rankings

Classes

- [11/10-15/10] #00 - Introduction to the course and the online judge
- [18/10-22/10] #01 - Sublinear complexity data structures (map, set, priority_queue)
- [25/10-29-10] #02 - Sorting, binary search, ternary Search, bisection
- [01/11-05/11] #03 - Sqrt decomposition, segment trees and variants
- [08/11-12/11] #04 - Cumulative sums and fenwick trees (BITs)
- [15/11-19/11] #05 - Dynamic Programming I (classic)
- [22/11-26/11] #06 - Dynamic Programming II (partitions, games, dags, counting, search)
- [29/11-03/12] #07 - Graphs I (DFS, BFS, topological sorting, articulation points, bridges, euler paths, ssc)
- [06/12-10/12] #08 - Graphs II (distances: dijkstra, bellman-ford, floyd; MST: prim+kruskall; max flow)
- [13/12-17/12] #09 - Strings (KMP, Aho-Corasick, tries, suffix trees, suffix arrays)
- [03/01-07/01] #10 - Computational Geometry (points, lines, polygons, intersections, areas, inclusion, convex hull)

Online Judges

- Student's IDs on the online judges (editable spreadsheet)
**Main online judges that will be used on this course:****[VJudge]**Virtual Judge*("meta" judge that allows you to submit on any judge)***[UVA]**Valladolid Online Judge | uHunt | uDebug**[SPOJ]**Sphere Online Judge | uDebug**[CF]**CodeForces**[Kattis]**Kattis

- Other online judges: AtCoder ICPC Live Archive | PEG | Timus | DM:OJ
- Other online contests/communities: Google Code Jam | CodeChef | HackerRank | Topcoder | IPSC | Project Euler
- USA integrated training program: USACO

Study Material

- Awesome Competitive Programming
**[recommended]**

*(A curated list of awesome Competitive Programming, Algorithm and Data Structure resources)*

**Main recommended books (available for free):****Other books:****Algorithmic Tutorials:**- TopCoder: Competitive Programming Tutorials
- MAXimal: E-Maxx Algorithms in English | (original in russian)
- PEG: PEG Wiki
- Geek for Geeks: Fundamentals of Algorithms | How to prepare for ACM-ICPC?
- CodeForces: Good Blog Post Resources about Algorithm and Data Structures
- Codechef: Data Structures and Algorithms
- South Africa IOI Training Material

**Implementations/Notebooks***(you are strongly advised to implement by yourselves before seeing how others did)*- CodeLibrary (Java and C++) | Github
- Stanford Notebook (C++) | Github
- spaghetti-source (C++)

Other Similar Courses

- 15-295: Competition Programming and Problem Solving (CMU, USA)
- CS104c: Competitive Programming (UTAustin, USA)
- CS3233 - Competitive Programming (NUS, Singapura)
- CS 97SI: Introduction to Programming Contests (Stanford, USA)
- T-414-ÁFLV: A Competitive Programming Course (Reykjavik University, Iceland)

Pedro Ribeiro - DCC/FCUP |
**Last update:**