2024 Introduction to Competitive Programming

2024 / 2 / 21

Course Administration

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

https://discord.gg/uaBpzZJWhN

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.

  • ICPC playoff

    • 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)

Winter Camp Course

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)

  • Ocean Cup

    • 1% + 0.5% per solved problem

  • HP code wars?

    • 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

Select a repo