Category: Algorithm
Eulerian Path
Posted on
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. We have the following properties for undirected graph, An undirected graph has an Eulerian cycle if and only if every vertex has even…
The Manacher’s Algorithm Template
Posted on
The Manacher algorithm is a linear algorithm to calculate the total number of palindromic substring of the given string (also the longest palindromic substring). The problem has other solutions, including O(n^2) dynamic programming and O(nlogn) rolling hash + binary search result. Reference https://cp-algorithms.com/string/manacher.html
Binary Exponentiation Template
Posted on
The recursion version is not slower than the while loop version when it is o2 optimized or above. See https://godbolt.org/z/E9jYefrKG.
Reservoir Sampling
Posted on
Given an infinite stream (or a finite sequence of size n), choose k numbers randomly.
Fisher–Yates Shuffle
Posted on
Generating a random permutation of a finite sequence. O(n^2) The basic method given for generating a random permutation of the numbers 1 through N goes as follows: Write down the numbers from 1 through N. Pick a random number k between one and the number of unstruck numbers remaining (inclusive). Counting from the low end, strike out the kth number not…
Modular Multiplicative Inverse
Posted on
If we have a * x = 1 (mod kMod), we call x is a multiplicative inverse of a when modular is kMod (in this post, kMod is a prime number). Usually we use a^-1 to represent it. Binary Exponentiation Given a and kMod, we can get a^-1 in O(logkMod) time. Dynamic Programming This solves…
LCA (Binary Lifting) Template
Posted on
Rolling Hash Template
Posted on
With a Prime Modular 2^64 as a Modular Two Hash Functions
Segment Tree Template
Posted on
Range Update Index Update
Prime Factorization
Posted on
The this post, we introduced how to get all prime numbers from 1 to n in o(nloglogn) time. Base on which, we can do prime factorization in O(logn) time.
Prime Numbers
Posted on
Prime Numbers in [1, n] The naive method takes O(n^1.5)) time. We could use the famous Sieve of Eratosthenes algorithm.
Sliding Window Concepts
Posted on
The Sliding Window technique is usually used to find the shortest or longest qualified subarray. For example, find the shortest subarray whose sum is no less than K. A Naive Idea The problem is straightforward if, for every right index, we could find the rightmost left index so that the window has sum >= K….
Minimum Spinning Tree
Posted on
Summary A spanning tree of some graph G is a subgraph that is a tree which includes all of the vertices of G, with a minimum possible number of edges. A Minimum Spanning Tree (MST) is a spanning tree whose sum of edge weights is as small as possible. Kruskal’s Algorithm Please refer to this page for its concepts and pseudo codes. The following code…
Eulerian Path
Posted on
Summary An Eulerian path is a path in a finite graph that visits every edge exactly once (allowing for revisiting vertices). An Eulerian cycle is a Eulerian path that starts and ends on the same vertex. We give the following properties without proof. An undirected graph has an Eulerian trail iif exactly 0 or 2 vertices have odd degree, its…
Lowest Common Ancestor
Posted on
Summary Lowest Common Ancestor (LCA) is a typical rooted tree related problem. A simple solution is use dfs to traverse the graph from root to leaves. If at some point it is first time we find out two nodes are in the same subtree, the current node is the LCA. The solution costs O(n) time….
Quick Select & Quick Sort
Posted on
Summary Quick Select is typical technique to select the top k elements (the rest of array is not sorted) from an array in amortized O(n) time. If we use a smart way to choose pivot (Introselect), the algorithm is guaranteed to have O(n) worst case performance. Quick Sort is an unstable sort. It has amortized…
Shortest Path
Posted on
Summary A common problem in undirected or directed graph is to calculate the shortest path between two nodes. There are several typical technologies that we could use. Floyd-Warshall Shortest paths (multiple sources) in such graphs that: It is actually a DP problem. We define alg[k][x][y] as the shortest path from x to y using the…
Calculator
Posted on
Summary There are a number of questions in the form that given a string, evaluate the value of it. These questions can be all solved by the routine Infix Notation to Reverse Polish Notation and Evaluate Reverse Polish Notation.
Bit Manipulation Tricks
Posted on
Summary Bit manipulation is all about tricks. bitset is also a common data structure in set problems. Details Bitwise Not Flip Last Set Bit The last set bit is the rightmost set bit. i&(i-1) does the trick to reset that bit. It is commonly used in Binary Indexed Tree (BIT). (i-1) flips all the bits…
Pure Geometry
Posted on
LC 1453. Maximum Number of Darts Inside of a Circular Dartboard Given 2 points and 1 radius, there will be 2 or 1 or 0 circles where the 2 points are at the boundary. When dist(p0, p1)>2r, there will be 0 circles. The difficulty is how to get the center of the circle in clean…
DP in Linear Structures (Extra States)
Posted on
Summary In some problems, the index i is not enough to make subproblems alg[i] independent to the previous sequences s[0,i-1]. We need one or several extra states to make subproblem self-contained. The intuition is: if we brute force the problem, there might be many duplicate visitings. For example, two different dfs enter the same index…
Monotonic Queue Concepts
Posted on
Summary Usually, the monotonic queue can be used in the following situations. Next Greater/Greatest: find the first larger or smaller element (or the largest or smallest element) from the current index to the very right index; Sliding Window Max: find the smallest or largest value in a sliding window Length s.t. Max: find the longest…
DP in Intervals (Break on Boundaries)
Posted on
Summary In this category, given a range alg[i,j], the subproblem is usually reduced to alg[i+1,j], alg[i,j-1], or alg[i+1,j-1] according to the properties of boundaries i and j.
DP in Intervals (Extra States)
Posted on
Summary In this category, given a range alg[i,j], the subproblem is not self contained. To make the subproblem independent to outer ranges, some extra states need to be added.
DP in Intervals (Break in Middle)
Posted on
Summary In this category, given a range alg[i,j], we need to identify a middle point k and change the problem into alg[i,k] and alg[k+1, j]. Details LC 375. Guess Number Higher or Lower II Once we identify this problem as a DP problem, it is not difficult. Given a number from 1 to n, actually…
Sliding Window & Monotonic Queue
Posted on
Summary A typical sliding window problem requires the longest or shortest subarray which satisfies certain constraints. The constraint must satisfy a monotonic property: as the right end of the window increases, the left end won’t decrease. If the constrain is related to maximum or minimum, we could use Monotonic Queues, which are perfect data structures…
Rolling Hash
Posted on
Summary Rolling hash is a common technique to compare if two substrings are equal or not. Given O(n) preprocessing time, the comparison becomes O(1) at the best case. OJ Details We use two large coprime numbers for base and for mod. We use a polynomial to calculate the hash value. Typical values are and …
Combination & Permutation & DP Counting
Posted on
Summary A majority of DP counting problems would define a rule of combination or permutation, under which, you have to calculate the total number of different combinations or permutations. Some typical rules and corresponding solutions are listed below. At most x same consecutive elements; the solution is to use a dimension to record the consecutive…
Monotonic Queue in DP
Posted on
Summary In this post, I will introduce some DP problems involving the Monotonic Queue. Details LC 1425. Constrained Subset Sum It is not difficult to get the following O(n^2) solution. However, the complexity is not good. What we need for {alg[i+j] for j=[1, k]} is only the maximum. So we need to keep tracking the…
Reduce Time Complexity in DP
Posted on
Summary In this post, I will introduce some DP problems. It might not be difficult at the first glance. However, the optimal solution might have lower complexity if one carefully defines the state or uses some other techniques while transferring states. OJ Details LC 1027. Longest Arithmetic Sequence It is not difficult to get the…
State Compression DP
Posted on
Summary State compression is a common technique in some DP problems when number of states are limited and each state consists of bits, where each bit has specific physical meaning. OJ Details LC 1349. Maximum Students Taking Exam Difficulty: 6 points. We could use bit manipulation and state compression DP. For each row, when a…
Built-in C++ String Functions
Posted on
This post contains some useful functions in the standard library which simplify your codes regarding string processing. std::rotate* Performs a left rotation on a range of elements. Specifically, std::rotate swaps the elements in the range [first, last) in such a way that the element n_first becomes the first element of the new range and n_first…
Linear Recurrence Relation & Binary Exponentiation & DP Counting
Posted on
Summary In this post, I will introduce a common technique in some DP counting problems: binary exponentiation. Typically, in these problems, you will be given a number n and you are asked to return the number of valid combinations. You need to figure out the initial state and the transform function between states. The problems…
Hard-to-Detect DP
Posted on
Summary In this post, I will introduce some problems that seem difficult. But once we think of them in another way, they will become DP problems in linear structures or intervals, which are not difficult to solve. OJ Details LC 1049. Last Stone Weight II Think of it in this way: we divide the numbers into…
Pure Greedy
Posted on
Summary In this post, I will introduce some problems which could solved by pure greedy technique. “Pure” means no other techniques are needed in this category of problems. Actually greedy can be combined by other techniques like DP. Note that usually greedy will be faster than Pure Dynamic Programming. But in case one could not…
Binary Search the Result
Posted on
Summary In this post, I will introduce some problems which could binary search the best result. The problems in this category usually ask for a best value. The value could fall into the range of [min, max]. Another important property is that if the value at the middle is not achievable, we could eliminate a…
Palindrome & DP
Posted on
Summary In this post, I will introduce some problems related to palindrome and dynamic programming. A palindrome has a property that, if we add two equal characters in both side of it, it is still a palindrome. OJ Details LC 1278 Palindrome Partitioning III Difficulty: 6-7 points Given a string s containing lowercase letters and an integer k….
Merge Sort
Posted on
Summary In this post, I will introduce some problems using the merge sort technique. These problems often ask, for an element at index , how many are there which satisfies a formula. OJ Details The Master Theorem If is of complexity , then is of complexity So in these problems, a key point…
DP in Linear Structures & Real Result
Posted on
Summary Some problems require returning real result not just a number. To do this, a good method is that we create another table to store the optimal choices we made on each state. To return any optimal result, the choice table will be as large as the alg table. The result can we achieved by…
Divisors & Factors
Posted on
Summary In this post, I will introduce some common techniques related to divisors and factors. Details Number of Divisors GCD
KMP
Posted on
Summary In this post, I will introduce some problems related to KMP. OJ Details Pi is the length of the longest prefix of substring , such that this prefix is also the suffix of . Note that this prefix excludes itself. By the definition, we have . For example, we have, Please refer…
Pure Bit Manipulation
Posted on
Summary In this post, I will introduce problems related to bit manipulation. Before that, you may want to learn the std::bitset<> class template. Detials LC 1386. Cinema Seat Allocation The problem is not difficult. But it is tricky to write a clean code. The hint is that all valid patterns can be presented by the…
Monotonic Queue (Pure)
Posted on
Summary I will introduce some pure Monotonic Queue problems in this post. Details Sword to Offers Problem 59 Max Queue Mantain a special queue so that you can do max_value, push_back, and pop_front in amortized O(1) time. LC 456. 132 Pattern It is not difficult to get an O(n^2) or even an O(nlogn) solution: we…
Segment Tree
Posted on
Summary In this post, I will introduce several templates for the Segment Tree. Compared to the binary index tree, segment tree is easy to understand, though the codes are longer. I will not introduce 2D Segment Tree in this post. Some OJ problems are listed below. LC 1157: query range majority; update single node; LC…
DP in Intervals (Dynamic)
Posted on
Summary Some problems in this category has something dynamic. Like several elements merge into one element or eliminate one element with the a cost related to its neighbors. The key point of these problems is think backward: think about how the last element is formed. Details Minimum Cost to Merge Stones I There are N…
Date
Posted on
Summary In this post, I will introduce some problems related to date. Details Is Leap Year Days of the Year Days from 1900 Days Between Dates