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 …

# Month: April 2020

## Combination & Permutation & DP Counting

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

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

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

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

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

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

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

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

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…

## Subarray & DP

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…