ACM Large Problem Set
ACM Large Problem Set
There are many problem sets available online, most of which can be evaluated online, hence called Online Judge. Except for USACO, which is prepared for IOI, almost all others are university ACM competition problem sets.
USACO
http://ace.delos.com/usacogate
A well-known online problem set in the United States, specifically prepared for informatics competition participants.
TJU
Tongji University online problem set, the only Chinese problem set, suitable for NOIP participants.
ZJU
Zhejiang University online problem set.
JLU
Jilin University online problem set (often inaccessible).
PKU
Peking University online problem set.
URAL
Ural Federal University online problem set.
SGU
Saratov State University online problem set.
ELJ
http://acm.mipt.ru/judge/bin/problems.pl?lang=en
Moscow Institute of Physics and Technology.
SPOJ
Gdańsk University of Technology in Poland.
UVA
Online problems from Universidad de Valladolid in Spain.
ACM Contact Suggestions
A suggestion from an expert:
Generally, aim to write programs of less than 50 lines without debugging, and debug programs of less than 100 lines within two minutes. ACM mainly tests algorithms, and most of the time should be spent thinking about algorithms, not on writing programs and debugging.
Here’s a plan for you to practice:
Phase One:
Practice classic commonly used algorithms, write each of the following algorithms ten to twenty times, while simplifying your code,
because they are too commonly used, you should practice until you can write them without thinking, finishing in 10-15 minutes, even being able to write the program with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Number (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, checking line segment intersection, then write a convex hull.
- BFS, DFS, while becoming proficient with hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, master them slowly.
- Conversion between any bases.
Phase Two:
Practice slightly more complex but also commonly used algorithms.
For example: - Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoized DP
- Game theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Phase Three:
The first two phases are foundational, the third phase is to train to quickly establish models and think of new algorithms during competitions. This requires practicing comprehensive problem types regularly. - Read papers on OIBH (there are hundreds of them, I’ve only read a little, haha).
- Regularly scan difficult problems on ZOJ, don’t always do those that don’t require thought. (The moderator of the ACM at Zhongda often says I choose simple ones to do :-P)
- Participate in online competitions to feel the atmosphere of competition and assess your own strength.
- Don’t just consider a problem solved once you’ve passed it; ask others if there are better algorithms and try them out.
- Keep good records of the problems you’ve solved. :-)
ACM ICPC Learning Plan
A plan from an expert—
Generally, aim to write programs of less than 50 lines without debugging, and debug programs of less than 100 lines within two minutes. ACM mainly tests algorithms, and most of the time should be spent thinking about algorithms, not on writing programs and debugging.
Here’s a plan for you to practice:
Phase One: Practice classic commonly used algorithms, write each of the following algorithms ten to twenty times, while simplifying your code,
because they are too commonly used, you should practice until you can write them without thinking, finishing in 10-15 minutes, even being able to write the program with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Number (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, checking line segment intersection, then write a convex hull.
- BFS, DFS, while becoming proficient with hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, master them slowly.
- Conversion between any bases.
Phase Two: Practice slightly more complex but also commonly used algorithms.
For example: - Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoized DP
- Game theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Relevant Knowledge
Graph Theory
Path Problems
0/1 Edge Weight Shortest Path
BFS
Non-negative Edge Weight Shortest Path (Dijkstra)
Characteristics of problems solvable by Dijkstra
Negative Edge Weight Shortest Path
Bellman-Ford
Yen's Optimization for Bellman-Ford
Difference Constraint System
Floyd
General Path Problems
Transitive Closure
Minimax Distance / Maximin Distance
Euler Path / Tour
Cycle-Cycle Algorithm
Euler Path / Tour for Mixed Graphs
Hamilton Path / Tour
Construction of Hamilton Path / Tour for Special Graphs
Spanning Tree Problems
Minimum Spanning Tree
k-th Smallest Spanning Tree
Optimal Ratio Spanning Tree
0/1 Fractional Knapsack
Degree Limited Spanning Tree
Connectivity Problems
Powerful DFS Algorithm
Connectivity of Undirected Graphs
Articulation Points
Bridges
Biconnected Components
Connectivity of Directed Graphs
Strongly Connected Components
2-SAT
Minimum Vertex Cover
Directed Acyclic Graphs
Topological Sorting
Relationship between Directed Acyclic Graphs and Dynamic Programming
Bipartite Graph Matching Problems
Conversion Ideas between General Graph Problems and Bipartite Graph Problems
Maximum Matching
Minimum Path Cover for Directed Graphs
Minimum Cover for 0/1 Matrices
Perfect Matching
Optimal Matching
Stable Marriage
Network Flow Problems
Simple Characteristics of Network Flow Models and their Relationship with Linear Programming
Max Flow Min Cut Theorem
Maximum Flow Problems
Maximum Flow Problems with Upper and Lower Bounds
Circulation Flow
Minimum Cost Maximum Flow / Maximum Cost Maximum Flow
Properties and Determination of Chordal Graphs
Combinatorial Mathematics
Common Ideas for Solving Combinatorial Mathematics Problems
Approximation
Recursion / Dynamic Programming
Probability Problems
Polya's Theorem
Computational Geometry / Analytical Geometry
Core of Computational Geometry: Cross Product / Area
Main Force of Analytical Geometry: Complex Numbers
Basic Shapes
Points
Lines, Line Segments
Polygons
Convex Polygons / Convex Hull
Introduction of Convex Hull Algorithms, Convex Hull Wrapping Method
Graham's Scan Method
Introduction of Horizontal Sequences, Patching for Collinear Convex Hulls
Perfect Convex Hull Algorithm
Related Determination
Intersection of Two Lines
Intersection of Two Line Segments
Determining if a Point is Inside Any Polygon
Determining if a Point is Inside a Convex Polygon
Classic Problems
Minimum Enclosing Circle
Approximate O(n) Minimum Enclosing Circle Algorithm
Diameter of a Point Set
Rotating Calipers, Antipodal Points
Triangulation of Polygons
Mathematics / Number Theory
Greatest Common Divisor
Euclidean Algorithm
Extended Euclidean Algorithm
Congruence Equations / Binary Linear Indeterminate Equations
Systems of Congruence Equations
Systems of Linear Equations
Gaussian Elimination
Solving Linear Equations over mod 2
Exact Solutions for Integer Coefficient Systems
Matrices
Calculating Determinants
Using Matrix Multiplication to Quickly Calculate Recursion Relations
Fractions
Fraction Trees
Continued Fraction Approximations
Number Theory Calculations
Finding the Number of Divisors of N
Finding phi(N)
Finding the Sum of Divisors
Fast Number Theoretic Transform
……
Prime Number Problems
Probabilistic Primality Testing Algorithms
Probabilistic Factorization
Data Structures
Organizational Structures
Binary Heaps
Leftist Trees
Binomial Trees
Winner Trees
Skip Lists
Style Icons
Splay Trees
Reap
Statistical Structures
Fenwick Trees
Virtual Binary Trees
Segment Trees
Rectangular Area Union
Circular Area Union
Relational Structures
Hash Tables
Union-Find
Application of Path Compression Ideas
Data Structures in STL
Vector
Deque
Set / Map
Dynamic Programming / Memoized Search
Differences in Thinking between Dynamic Programming and Memoized Search
Longest Subsequence Series Problems
Longest Non-decreasing Subsequence
Longest Common Subsequence
Longest Common Non-decreasing Subsequence
Dynamic Programming Solutions for a Class of NP Problems
Tree Dynamic Programming
Knapsack Problems
Optimization of Dynamic Programming
Quadrilateral Inequality
Convexity of Functions
State Design
Planning Direction
Linear Programming
Common Ideas
Binary
Minimum Representation
Strings
KMP
Trie Structure
Suffix Trees/Suffix Arrays
LCA/RMQ
Finite State Automata Theory
Sorting
Selection/Bubble
Quick Sort
Heap Sort
Merge Sort
Radix Sort
Topological Sort
Sorting Networks
Proficiently Master Data Structures, Common Algorithm Aggregation
(1)
It is impossible to completely memorize so many algorithms.
Common algorithms can be written out directly.
Uncommon ones can be understood by looking at the book for 10 minutes (because they were memorized before).
For algorithms that have not been memorized before, it is hard to say; difficult ones may require several days of study.
That’s enough.
The commonly used algorithms that should be proficiently mastered include:
Various sorting algorithms (insertion sort, bubble sort, selection sort, quick sort, heap sort, merge sort)
Insertion and deletion of linear lists (general linear lists, stacks, queues)
Traversal of binary trees (pre-order, in-order, post-order)
Traversal of graphs (depth-first, breadth-first)
Binary search, sorted binary trees, hash search (methods for handling conflicts).
(2)
When analyzing something, you can look at it from different perspectives; many times, it’s like life itself. You feel that the way you viewed problems as a child was naive, but now you see problems more comprehensively and in different ways. Why? It’s just growth; it’s the same with algorithms. For example, writing a program may seem simple, but there can be interesting ways to express it and make it more efficient, etc.
(3)
In college, solidify the basics of your major courses, such as data structures, discrete mathematics, operating systems, etc. When encountering basic data structures and algorithms, such as searching and sorting, you should be able to write the corresponding code immediately based on the principles. This is my personal understanding; for deeper topics, it is also built on a solid foundation of familiarity.
(4)
"Analysis of Algorithm and Data Structure Test Questions" 2nd Edition, Mechanical Industry Press
If you want to practice, there are many questions here to practice, but in reality, few can be used unless you are doing some high-end stuff. However, you can also combine them in your projects.
(5)
Data structures may not be used often, but they can cultivate your awareness of efficiency when programming. A person who has studied data structures may write programs that are more efficient than someone who has not studied them.
(6)
Master the algorithms needed for ACM.
It should be noted that ACM competitions are highly competitive, so you should relate yourself to your actual applications.
What suits you is good; some people are not suited for algorithms but prefer system architecture, so don’t be envious of what others do.
Play to your strengths; that’s what’s important.
Phase One: Practice classic commonly used algorithms, write each of the following algorithms ten to twenty times, while simplifying your code,
because they are too commonly used, you should practice until you can write them without thinking, finishing in 10-15 minutes, even being able to write the program with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Number (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, checking line segment intersection, then write a convex hull.
- BFS, DFS, while becoming proficient with hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, master them slowly.
- Conversion between any bases.
Phase Two: Practice slightly more complex but also commonly used algorithms.
For example:
- Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoized DP
- Game theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Phase Three: The first two phases are foundational, the third phase is to train to quickly establish models and think of new algorithms during competitions. This requires practicing comprehensive problem types regularly.
- Read papers on OIBH (there are hundreds of them, I’ve only read a little, haha).
- Regularly scan difficult problems on ZOJ, don’t always do those that don’t require thought. (The moderator of the ACM at Zhongda often says I choose simple ones to do :-P)
- Participate in online competitions to feel the atmosphere of competition and assess your own strength.
- Don’t just consider a problem solved once you’ve passed it; ask others if there are better algorithms and try them out.
- Keep good records of the problems you’ve solved. :-)