Competitive Programming (CC3032) | |

Pedro Ribeiro - DCC/FCUP |

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

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

Evaluation

- Evaluation Formula
**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:
**24 Oct***(onsite, all or nothing like ICPC or CodeForces/AtCoder round)* - 2nd Contest:
**06 Jan, 09:00, FC6 008***(onsite, partial points per problem like IOI)* - 3rd Contest:
**19 Jan, 14:30, FC6 008***(on site, partial points per problem like IOI)*

- 1st Contest:

Lists and Rankings

(Predicted) Classes

- [19/09] #00 - Introduction to the course and the online judge
- [26/09] #01 - Sublinear complexity data structures (map, set, priority_queue)
- [03/10] #02 - Sorting, binary search, ternary Search, bisection
- [10/10] #03 - Sqrt decomposition, segment trees and variants
- [17/10] #04 - Cumulative sums and fenwick trees (BITs)
- [24/10]
**1st OnSite Contest** - [31/10]
**No Classes (FCUP Activities Week)** - [07/11] #05 - Dynamic Programming I (classic)
- [14/11] #06 - Dynamic Programming II (partitions, games, dags, counting, search)
- [21/11] #07 - Graphs I (DFS, BFS, topological sorting, articulation points, bridges, euler paths, ssc)
- [28/11] #08 - Graphs II (distances: dijkstra, bellman-ford, floyd; MST: prim+kruskall; max flow)
- [05/12] #09 - Strings (KMP, Aho-Corasick, tries, suffix trees, suffix arrays)
- [Jan]
**[optional]**#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**[AtCoder]**AtCoder**[CSES]**CSES

- Other online judges: PEG | Timus | DM:OJ
- Other online contests/communities: Google Code Jam | CodeChef | HackerRank | Topcoder | Project Euler | IPSC
- 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

**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:**