CSE348

Introduction

This is the official git repository of Computer Science and Engineering 348 T.

ICPC is the world's largest and most prestige algorithm competition for college students. It contains a whole series of events from regional contests all the way to world finals. It is the best way to showcase your algorithm knowledge and impress recruiters, on top of your internship, curriculum, and research experience.

Breakdown and Timeline

Here is the (not so) typical timeline for 2022-2023 ICPC competitions.

NAQ (Qualifier: North America Qualifier, 2023-02-04)

This is the competition that most schools use ask a way of selecting contestants and teams. We have participated in the qualifier every year and usually we pick the top 15 students who are willing to compete. Teams are mostly selected based on candidates' results in the qualifier and their preferences. Since each school only has one spot to advance, the top 3 candidates in the qualifier usually prefer to team up and try out for the next level.

Problems at this stage includes LeetCode easy, median, hard (which are introductory-level competition programming), as well as a few intermediate-level problems.

For organizer: remember to reserve rooms for the qualifier so that most of the contestants can work on the problems in person.

Link: 19 20 21 22 23

MCPC (Regional: Mid-Central Programming Contest, 2023-02-25)

This is the competition where we face other contestants from school in the Mid-Central Region. Touch schools includes UIUC, UChicago, Truman State, Rose-Hulman, Kentucky, etc. We usually need to be the top 5 schools in the region to advance to the national championship (each school is capped at one team). In the case when there is a divisional competition between the regional and the national, we need to be the top 12 schools (each school is capped at two teams).

Problems at this stage includes LeetCode easy, median, hard (which are introductory-level competition programming), but the majority are intermediate-level problems.

For organizer: remember to apply for funding for a minibus or sprinter that can host 15 people as early as possible. The process can take up to 2 months.

Link: 19 20 21 22 23

NAC (National: North America Championship, 2023-05-25 ~ 30)

This is when the competition starts to get really series. We are facing all the schools that have loud names, MIT, Waterloo, Toronto, etc., where teams are made up of former IOI Gold medalists in high school. Starting from this level, the competition will be a multi-day event and there will be recruiting events held on site, where you can talk to recruiters from big techs, national defense and quants. In the recent years, We have sent people to NAC in 2019 and 2023.

Problems at this stage includes one LeetCode median (as the so-called check-in problem). Then, one or two very hard LeetCode hard, a few intermediate-level problems, and many advanced problems.

For organizer: remember to apply for funding for the plane tickets once you're qualified. The process can get lost or the request can get disapproved, since the travel time are in the summer (not in the semester).

Link: 20 21 22 23

ICPC World Final (it was jointly held with the prior year's world final due to COVID-19)

This is the surreal competition that everyone wants to get in, but few could have the ticket for it. You will see geniuses from around the world, and the competition is really series. Folks from Europe and Asia as more than some try-hard contestants. WashU is proud to be part of this game in 2017 and 2018. What is more, we got Rank 24 world-wide in 2017!

Technical Resources

For practicing in your own time, we recommend Kattis, as this is the official site used for NAQ, MCPC, and NAC series. Codeforces for more competitive problems. LeetCode is also good sources for a more balanced practice between competitiveness and interview.

Human Resources

Tim Dong: Organizer of WashU ICPC/LeetCode practice from 2019-2023, owner of this repo. Contact me at here if you have any questions about prior experiences.

Yiheng Yao: Former President of ACM, contributor of this repo.

Yuheng Ding: North America Championship contestant, contributor of this repo.

Prof. Cosgrove: The Professor contact of this event. He is the veteran in WU ICPC.

Prof. Ju: Veteran in collegiate-level math competition, might also be interested in ICPC.

Prof. Corwin: The director of Mid-Central regional. He manages a mailing list that is very helpful (for logistics). Too add you to the email list, or if you have other questions, reach out to him at here.

Student Union, McKelvey: Where we get money to travel, and more!

Topics in Competitive Programming

• References
  • https://cp-algorithms.com (English, contains machine-translation from the oi-wiki)
  • https://oi-wiki.org (Chinese)
• Basics
  • Simulation / Implementation
• Data Structure
  • Standard Templates Library
    • LinkedList
    • Stack / PriorityQueue
    • Queue / Deque
    • Set / Multiset / Map / Multimap
    • HashSet / HashMap
  • Optimization
    • Prefix-Sum
    • Disjoint-Set (Union Find)
    • Fenwick Tree (Binary Indexed Tree)
    • Segment Tree
    • Tries
• Solution Paradigms
  • Brute Force
  • Binary Search / Binary Lifting
  • Recursion
    • Memorized Search
  • Dynamic Programming
    • Standard
    • Interval
    • Circular
  • Divide and Conquer
  • Greedy Algorithm
  • Sliding Window
  • Monotonic Queue
• Graph Theory
  • Tree
    • Least Common Ancestor
  • Searching and Traverse
    • Breath-First Search
    • Depth-First Search
  • Minimum-Spanning Tree
    • Prim's Algorithm
    • Kruskal's Algorithm
  • Shortest Path
    • Dijkstra's Algorithm / A*
    • Bellman-Ford Algorithm / SPFA
    • Floyd-Warshall Algorithm
  • Network Flow
    • Max-Flow / Min-Cut
• Mathematics
  • Probability
  • Combinatorics
  • Number Theory
  • Computational Geometry
• String Processing
  • Knuth-Morris-Pratt Algorithm
  • Aho–Corasick Algorithm
• Optimization (ad hoc)
  • Bit-mask Optimization
  • Pre-computation