ACM ICPC Materials

This repository contains ACM-ICPC preparation materials used by our ICPC training group, including answers to Kattis problems and code templates.

Official Websites

• North America Qualification Contest: http://cs.baylor.edu/~hamerly/icpc/
• East Central North America Regional: http://acm-ecna.ysu.edu/
• World Final: https://icpc.baylor.edu/

Practicing Materials

Online Judges

• Kattis: https://open.kattis.com/
  • 2017 North America Qualifier Contest: Contest - Open Section - Answer and Analysis
  • 2016 North America Qualifier Contest: Contest - Open Section - Answer and Analysis
  • 2015 North America Qualifier Contest: Contest - Open Section - Answer and Analysis
  • 2017 East Central NA Reginal Contest: Contest - Answer
  • 2016 East Central NA Reginal Contest: Contest - Answer
  • 2015 East Central NA Reginal Contest: Contest - Answer
• USACO: http://train.usaco.org/usacogate
• CodeForces: http://codeforces.com/
• Hackerrank: https://www.hackerrank.com/
• POJ: http://poj.org/

Roadmaps

• POJ Training Roadmap (in Chinese): http://blog.csdn.net/a1dark/article/details/11714009

Reading Materials

Books

• M.H. Alsuwaiyel. Algorithms: design techniques and analysis, World Scientific Pub. Co. Inc. 1999.
• S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani. Algorithms, 2006
• T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, Third edition, 2009
• R. Sedgewick, K. Wayne. Algorithms, Fourth edition, 2011

Offline References

• C/C++:
  • cppreference.com
• Java:
  • Java SE 8 Doc
  • index.html -> Java SE API right bottom corner
• Python:
  • Python 3 Doc

Algorithms

For reference.

Basic Algorithms

• Divide and Conquer, Greedy, Simulating
• Sorting (Bubble Sort, Quick Sort)
• DFS (Stack-based), BFS (Queue-based)
• Dynamic Programming, Searching with Memorization

Data Structures

• Priority Queue (Binary Heap, Fibonacci Heap)
• Balanced Container (Skip List, Splay, Treap)
• Union Find
• Segment Tree, Binary Indexed Tree
• Hashing, Bitmap

Math

• Fast Matrix Exponentiation
• Large Number / High Precision
• GCD / LCM, Negative Carry System
• Prime Test (Eratosthenes, Miller-Rabin)
• Euler's Function, Eratosthenes, Chinese remainder theorem
• Gauss-Jordan, Simplex, FFT

Geometry

• Collision Detection, Intersection Test, Measure
• Convex Hull, Delaunay Triangulation

Graph

• Shortest Path (Dijkstra, SPFA, Floyd, A*)
• Minimum Spanning Tree (Prim, Kruskal)
• Strongly Connected Component (Tarjan)
• Eulerian Path (Hierholzer)
• TSP (Held-Karp)
• Topological Sort

Optimization

• Maximum Flow and Minimum Cut (Edmonds-Karp, Dinic, Push-relabel)
• Bipartite Matching
• Minimum Cost Maximum Flow and Matching
• Graph Cut Inference

String

• String Searching (Boyer-Moore, KMP, Aho-Corasick)
• Trie, Suffix Array