falling flowers

Learn✏️#

Basic Algorithms#

Simulation, Greedy, Enumeration, Binary Search, Prefix Sum, Difference, Divide and Conquer, Discretization, Search, Two Pointers

• Greedy: Think more, try pushing it a bit🧐

• Binary Search: Change your thinking, enumerate answers or certain constraints, note that the answer needs to have a certain property (usually monotonicity), the answer lies at the boundary where this property holds and does not hold, and there is only one at the boundary.

• Search: When greedy does not hold and there is no obvious verifiable property, you can perform a search. Remember to restore the initial state after deep search.

Basic Data Structures#

Sequential List, Linked List, Stack, Queue, Tree and Binary Tree, Heap/Priority Queue, STL Containers and Algorithms, Union-Find, Fenwick Tree, Sparse Table......

Be clear about which data structure to use in what situation, and what the complexity of various data structures for insert, delete, modify, and query is.

• Monotonic Stack/Monotonic Queue: The elements in the container must remain ordered at all times (if adding a new element makes it unordered, delete the one that entered first until it becomes ordered). Due to monotonicity, deleted elements cannot be the answer.

• Tree: Basic terminology of trees, properties of binary trees, special binary trees and their properties, three types of traversal methods for binary trees.

• STL Containers and Algorithms: Look at the documentation, remember spelling and initialization methods, and pay attention to time and space complexity.

• Union-Find: Important, path compression, union by rank, extended domain union-find (more relations) and weighted union-find (weight maintenance).

• Fenwick Tree: Important, maintains prefix sums, preprocessing takes $O(n \log n)$, both update and query time complexity are $O(\log n)$.

• Sparse Table: Mainly solves the RMQ (Range Maximum/Minimum Query) problem, using the doubling method, $O(n \log n)$ preprocessing, $O(1)$ query, st[i][j] represents the maximum value of the interval starting from $i$ with length $2^j$, i.e., the maximum value of the interval $[i, i + 2^j − 1]$, mainly remember preprocessing, querying, and whether properties can be derived from overlapping intervals.

Basic Dynamic Programming#

Difficult and important🥲, linear dp, interval dp, knapsack dp, bitmask dp, probability dp......

Dynamic programming is not a specific algorithm, but a method for solving specific problems. You need to understand its concept and ideas.

Dynamic programming is a method for solving complex problems by breaking the original problem down into relatively simple subproblems.

The idea of dynamic programming is to divide a problem into several subproblems for solving, and the implementation methods of dynamic programming can generally be divided into iterative method and recursive method.

When doing problems, you should first be able to see that dynamic programming is needed.

Various dp requires experience accumulation, do more problems😢.

Graph Theory#

DFS, BFS, Depth/Breadth First Traversal of Trees and Graphs, Topological Sorting, Dijkstra, Bellman-Ford, SPFA, Floyd, Prim.

Review often, don’t forget, practice a few more times to become familiar, remember the application scenarios and time complexity of various algorithms.

Mathematical Knowledge#

Prime numbers, divisors, Euler's function, fast exponentiation.

Same as above, if you don’t look at it for a few days, you’ll forget almost everything.

Also, modular arithmetic is very important, as well as bit manipulation.

Mistakes Made⚠️#

• Always manually verify a sample to ensure you understand the problem correctly before you start writing code.
  Don't write the code and then find a mismatch with the sample, realizing you misunderstood the problem😭.

• Do not reuse variable names, as it can easily lead to confusion and make it hard to find errors.

• unordered_map and unordered_set can get stuck😅, use map and set if possible.

• The size method of STL containers returns a type of size_t, which is the same as unsigned long long. Avoid performing subtraction on it, as it may lead to data overflow and cause infinite loops.

• When using a separate \n for line breaks, use single quotes; otherwise, unknown errors may occur.

• Pay attention to data ranges, and don't overflow int or make arrays too small.

• When there are multiple sets of test data, remember to initialize global variables.

• If a variable inside a function only has incremental operations, remember to assign a value during initialization.

• When changing types, remember to change the return type of the function; otherwise, it will lead to implicit conversion.

• By default, numbers are of int type; add the ll suffix to change to long long type. Similarly, decimals are of double type by default; add the l suffix to change to long double type.

• Do not perform equality checks on decimals, as there will be errors; use methods like abs(a - b) <= eps instead.

• When traversing a container, do not delete elements while traversing. If you must do so, it is recommended to use iterators to control access.

Tips💡#

If available, remember to select C++17 and enable O2 optimization.

Rolling arrays can use STL containers like vector's swap, efficiency is $O(1)$👍.

If variable names conflict with global variables during input, you can define the variable in the for initialization statement, like:

vector<int> p;
void solve() {
    for (int i = 1, p; i <= n; i++) {
      cin >> p;
      ::p.push_back(p);
    }
}

If pair cannot hold, you can also use tuple:

tuple<int, int, string> t;
get<0>(t) = 0;
get<1>(t) = 1;
get<2>(t) = "hello"s;

Positive infinity can be represented as 0x3f3f3f3f, and negative infinity can be represented as 0xcfcfcfcf.

The maximum value of the median can be solved by binary searching the answer and then binarizing it.

Others#

You need to supplement problems and write summaries.

Practice more and review often.

Competitions🏆#

Winter Training Individual Competition#

Codeforces#

Codeforces Round 996 (Div. 2)

• Score 2758
• AC 3/6
• Rating Change 1375 -> 1528

Codeforces Round 997 (Div. 2)

• Score 2369
• AC 3/6
• Rating Change 1528 -> 1499

Atcoder#

ABC388

• Score: 1000
• AC: 4/7
• Penalty: 33:25

ABC389

• Score: 950
• AC: 4/7
• Penalty: 36:21