LeBlanc’s law: "Later equals never".
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 …
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…
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…
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…
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…
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…
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…
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…
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…
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…
Summary In this post, I will introduce some problems related to subarray and dynamic programming. The most important thing in subarray is that it is continuous. So usually one dimension of the DP will be chosen as “a subarray starting at index i”. Then we need a separate loop for it to choose the best…