2024 Introduction to Competitive Programming
2024 / 2 / 21
Course Administration
course link
Lab location
- ECG 809
Coach
- William Hsu (Discord: wwyhsu#1083)
Co-Coach
- 高程昱 (Discord: jakao)
Lecturer
- 李欣祐 (Discord: LeeShoW)
- 胡智涵 (Discord: zihan8130)
TA hour
406, 407 in ECG 809
Course Group Link
Competitive Programming 4
作者： Steven Halim, Felix Halim, Suhendry Effendy
算法競賽入門經典（第2版）
作者： 劉汝佳
Competitive Programming
- Given well-known computer science problems, solve
them as fast as possible - Using Data Structure and Algorithm Solving them
- Teamwork
Goal
annual team contest
-
NCPC (National Collegiate Programming Contest)
-
ICPC (International Collegiate Programming Contest)
- for college students
- most prestigious programming contest in the world.
-
- around top 10-12 winner team (Except for the first place, each school at most 3 teams) in ICPC regional advance
- in Vietnam this year
Prerequisite knowledge
- Time Complexity
- Brute Force Algorithm
- Dynamic Programming
- Greedy
- Binary Search
- BFS/DFS
- Divide and Conquer
- Segment Tree (RMQ)
Course
-
Tree
- Lowest Common Ancestor
- DSU on Tree
- Heavy-Light Decomposition
-
Graph
- Shortest Path
- Topological Sort
- SCC/BCC
- 2-SAT
- Eulerian Path
-
Geometry
- Inner, Outer Product
- Line Intersection
- Convex hull construction
- Sweep Line
- Math
- Modulo Operation
- Modular Multiplicative Inverse
- Prime
- Gaussian Elimination
- Dynamic Programming
- DP on DAG
- Stack / Deque
- Bitmask DP
- 1D/1D Dynamic Programming
- DP on Tree
- Digit DP
- Data Structure
- Sparse Table
- Treap
- Persistent Data Structure
- String
- Trie
- Hash
- KMP
- Zvalue
Scoring
Basic (90%)
- Homework 20%
- Mock Contest 18%
- Midterm Exam 26%
- Final Exam 26%
Scoring
Bonus (10% up)
-
CPE 3/26, 5/21
- 1% (First 3 questions AC 2 problems)
- 1% per solved problem (Last 4 problems)
-
- 1% + 0.5% per solved problem
-
- 1% + 0.5% per solved problem
-
Online Contests(Codeforces, Atcoder) (5%)
- According to your participation times and contest performance
Personal Homework
補題，把上星期 Winter Camp Contest
problem BFJK 補完
submit to following link: https://codeforces.com/group/dnlUA4rsoS/contest/503770
deadline: 2/27 23:59
2024 Introduction to Competitive Programming 2024 / 2 / 21
{"slideOptions":"{\"transition\":\"fade\"}","description":"–type: slide","contributors":"[{\"id\":\"19f09ccf-6b99-452f-971f-955cfc1657f3\",\"add\":3638,\"del\":280},{\"id\":\"08326fa4-ca9b-4ca9-873e-239ebe76662c\",\"add\":318,\"del\":384},{\"id\":\"c09566ae-e372-4be1-b467-1ebdd3589721\",\"add\":3359,\"del\":3292}]","title":"2024 Introduction to Competitive Programming"}