2022 Introduction to Competitive Programming

2022 / 2 / 23

Competitive Programming

  • Given well-known computer science problems, solve
    them as fast as possible
  • Using Data Structure and Algorithm Solving them
  • Teamwork

contests

annual team contest

  • ICPC (International Collegiate Programming Contest)
    • for college students
    • most prestigious programming contest in the world.
  • NCPC (National Collegiate Programming Contest)

annual personal contest

  • GCJ (Google Code Jam)
  • FHC (Facebook Hacker Cup)
  • TCO (Topcoder Open)

daily training contest

practice

solving more problems

practice

participate more daily contest

learn

problem List

Course

  • Tree

    • Lowest Common Ancestor
    • DP on Tree
    • DSU on Tree
    • Heavy-Light Decomposition

  • Graph

    • Topological Sort
    • SCC/BCC
    • 2-SAT
    • Matching
    • Flow
    • Eulerian Path

  • String

    • Trie
    • Hash

  • Geometry

    • Convex hull construction
    • Sweep Line

  • Brute Force Search

    • Backtracking
    • Memory Search
    • Meet In the Middle

  • Math

    • Modulo Operation
    • Modular Multiplicative Inverse
    • Prime

  • Dynamic Programming

    • DP on DAG
    • Stack / Deque
    • Bitmask DP
    • 1D/1D Dynamic Programming

  • Data Structure

    • Sparse Table
    • Treap
    • Persistent Data Structure

  • Square Algorithm

    • Square Root Decomposition
    • Mo's Algorithm

Competitive Programming 4
作者： Steven Halim, Felix Halim, Suhendry Effendy

算法競賽入門經典（第2版）
作者： 劉汝佳

Course Administration

Lab location

  • CSE B18

Coach

  • William Hsu

Co-Coach

  • 高程昱 (Discord: jakao#5434)

Teaching assistant

  • 鄭子輿
  • 翁明緯

Score

  • Homeworks (Solo)
  • Mock Contests (Teams)
  • Midterm Exam (Solo)
  • Final Exam (Solo)
  • Ocean Cup Programming Contest ?
  • Bonus

Bonus

  • CPE 3/22, 5/24
    • 2% + 1% per solved problem
  • ITSA
  • HP Code Wars ?
    • 1% + 1% per solved problem
  • Online judge contests(Codeforces, Atcoder, Codechef, Topcoder…)
    • According to your participation times and contest performance

Faster typing

In ICPC、NCPC, you may bring 25 pages of codebook.

codebook

To solve easy problem quickly, capture the first blood!

Faster typing

  • Become a faster/better typist
  • Know your IDE (ICPC)
    • Vim, Codeblock, Eclipse
    • Visual Studio, Dev-C++

https://typing.io/
https://play.typeracer.com/
https://monkeytype.com/

測完打字速度來前面登記

Test

Test your basic coding skills

http://dom.aclab.cool

Create Team Account

using github
create a project to record your contest missing
and add codebook for team

https://github.com/fshp971/ACM-ICPC
https://github.com/wangyenjen/JAW/blob/master/world final report/icpc-report.pdf

Homework

補題，把上星期 Winter Camp Contest
problem BFHIJK 補完

提交到 https://codeforces.com/group/dnlUA4rsoS/contest/369935

3/1 23:59 截止

Select a repo