Note
This article is currently being edited and discussed. Feel free to supplement it with further learning roadmaps or share your thoughts in the comments!
This article introduces a learning roadmap for algorithmic competitions.
This learning roadmap is both a guide for beginners learning algorithmic competition knowledge and a review checklist.
1 C++ Language Basics
Start by learning C++ syntax, step by step.
1.1 Hello, World!
Begin your algorithmic competition journey with Hello, World!
At the same time, learn about the general structure of a C++ source program.
1.2 Variables and Operations
The original purpose of computers was calculation. So let us first learn how to complete some simple calculation tasks.
1.3 Flow Control
1.3.1 Branching Structures
Sometimes, we need to choose different statements to execute under different conditions; in such cases, we need to use branching statements.
Branching statements include the following types:
- if statements
- if-else statements
- if-elif-else statements
- switch statements
1.3.2 Loop Structures
To execute several statements repeatedly, we need to use loop statements.
Loop statements include the following types:
- for statements
- while statements
- do-while statements
1.4 Arrays and Structures
Arrays are used to store large amounts of data of the same type, while structures can bundle several variables together.
1.5 Functions and Recursion
Use functions to make programs modular and reduce implementation costs.
Recursion is a hurdle for beginners. “Calling itself” may not sound easy to understand, but after careful examination, you will find that “calling itself” is not essentially different from “calling someone else.”
2 CSP-J Beginner Level
2.1 Enumeration and Simulation
From now on, you can already use the C++ language to complete some simple tasks, but this is far from enough.
To solve some simple problems correctly, you need to learn to implement code by enumerating or simulating the logic in your mind. This may not look very efficient, but it is useful at times.
2.2 Recursion and Divide and Conquer
Recursion refers to repeatedly calling itself in a function definition; divide and conquer refers to repeatedly decomposing a problem into several subproblems, solving them, and then combining the results.
2.3 Strings
When solving informatics problems, strings are a data type you will often encounter. You need to learn some STL functions for operating on strings. Of course, simulation is also a good way to solve string problems.
2.4 Sorting
When you obtain a set of data, how to turn it from unordered into ordered is also an important problem. When you have no idea how to proceed, consider sorting the array. This is also the basis of many algorithms to come.
There are quite a few sorting methods, but they are not difficult to understand and remember once you have understood them.
- Introduction to Sorting
- Selection Sort
- Bubble Sort
- Insertion Sort
- Counting Sort
- Radix Sort
- Quick Sort
- Merge Sort
- Heap Sort
- Bucket Sort
- Sorting-Related STL
The NOI syllabus only requires the beginner level to learn selection sort, bubble sort, and insertion sort, three sorting algorithms in total. However, the others are not very difficult, and may also be involved in the preliminary round, so they are listed together here.
2.5 Binary Search and Doubling
Binary search essentially applies the idea of divide and conquer to continuously reduce the size of the search range until the answer is found. However, note that this search method must be applied to an ordered data structure.
Doubling is different: it repeatedly doubles in order to transform processing in the linear domain into logarithmic-scale processing, greatly optimizing the time complexity. (This topic requires some mathematical foundation, so it is also fine to skip it for now.)
2.6 Search
At the beginner level, search problems often appear in maze-type problems, which generally involve map-like data. In addition, search is also frequently used to efficiently enumerate and construct valid solutions, and can also be used to obtain partial scores.
2.6.1 Depth-First Search (DFS)
Depth-first search refers to an algorithm that uses recursive functions to conveniently implement brute-force enumeration. It is somewhat similar to the DFS algorithm in graph theory, but is not exactly the same.
2.6.2 Breadth-First Search (BFS)
By designing each state as a vertex in a graph, we can perform an exhaustive search.
2.6.3 Search Optimization
Many problems can be solved with DFS, but the complexity of this algorithm is clearly too high to pass. Therefore, some optimizations are needed to make it run faster. Such optimizations can reduce attempts that cannot succeed, and are called “pruning.” Optimizations related to BFS are more flexible, but the basic idea is the same here.
2.7 Introduction to Data Structures
2.7.1 Linear Data Structures
Arrays, linked lists, queues, and stacks are all linear structures. Making clever use of these structures can accomplish many convenient tasks.
2.7.2 Complex Data Structures
2.8 Introduction to Dynamic Programming
Dynamic programming (Dynamic Programming, DP) is a method for solving complex problems by decomposing the original problem into relatively simple subproblems.
Since dynamic programming is not a specific algorithm but a method for solving particular problems, it appears in all kinds of data structures, and the types of related problems are also more varied.
2.8.1 Knapsack Problems
That is, given a knapsack with limited capacity, choose several items with capacities and values to put into it, and determine how to place them so that the sum of the values is maximized. This is the first hurdle that blocks many OIers; from here on, algorithms become somewhat difficult to understand.
2.8.2 Linear Dynamic Programming
In dynamic programming, one of the most difficult parts is designing the state, which requires construction-related techniques. Once you have written the state and state transition equation, completing a dynamic programming problem is not difficult.
Memoized search is a search implementation method that records information about states that have already been traversed, thereby avoiding traversing the same state repeatedly. Some problems can also use memoized search to reduce the difficulty of reasoning.
Since memoized search ensures that each state is visited only once, it is also a common implementation of dynamic programming.
2.8.3 Complex Dynamic Programming
Interval dynamic programming is an extension of linear dynamic programming. When it divides a problem into stages, it has a strong relationship with the order in which elements appear in a stage and which elements from the preceding stage they are merged from.
2.9 Mathematics
2.9.1 High-Precision Algorithms
What if even long long (or int64) is not enough? Use a high-precision algorithm. Essentially, it simulates the four arithmetic operations.
2.9.2 Base Conversion
In computers, besides binary, octal and hexadecimal are also commonly used. Sometimes, learning to use the appropriate base is also very helpful for solving problems.
2.9.3 Bit Operations
Bit operations are operations based on the binary representation of integers. Since computers store data internally in binary, bit operations are quite fast.
There are 6 basic bit operations in total: bitwise AND, bitwise OR, bitwise XOR, bitwise NOT, left shift, and right shift.
2.9.4 Number Theory
- Number Theory Basics
- Primes
- Sieve Methods
- Greatest Common Divisor
- Euler's Totient Function
- Prime Factorization
2.9.5 Combinatorial Counting
At this point, you have finished learning all the algorithms in the beginner-level category. However, to master them, you need to continue solving a sufficient number of problems to consolidate the knowledge you have learned.