Read More

Read More

Read More

Read More

Read More

Read More

Read More

Read More

Read More

Read More

Skip to content
# Category: Algorithm

constexpr int kMaxN = 30'005; class RollingHash { public: using ll = long long; int hashes[kMaxN]; int bases[kMaxN]; int bases_reverse[kMaxN]; ...

Read More
Range Update constexpr int kMaxN = 100'001; using ll = long long; struct Info { int max; }; template <typename ...

Read More
The this post, we introduced how to get all prime numbers from 1 to n in o(nloglogn) time. Base on ...

Read More
Prime Numbers in [1, n] The naive method takes O(n^1.5)) time. // O(sqrt(a)) bool IsPrime(a) { if (a < 2) ...

Read More
The Sliding Window technique is usually used to find the shortest or longest qualified subarray. For example, find the shortest ...

Read More
Summary A spanning tree of some graph G is a subgraph that is a tree which includes all of the ...

Read More
Summary An Eulerian path is a path in a finite graph that visits every edge exactly once (allowing for revisiting ...

Read More
Summary Lowest Common Ancestor (LCA) is a typical rooted tree related problem. A simple solution is use dfs to traverse ...

Read More
Summary Quick Select is typical technique to select the top k elements (the rest of array is not sorted) from ...

Read More
Summary A common problem in undirected or directed graph is to calculate the shortest path between two nodes. There are ...

Read More
## Rolling Hash Template

## Segment Tree Template

## Prime Factorization

## Prime Numbers

## Sliding Window Concepts

## Minimum Spinning Tree

## Eulerian Path

## Lowest Common Ancestor

## Quick Select & Quick Sort

## Shortest Path

## Calculator

## Bit Manipulation Tricks

## Pure Geometry

## DP in Linear Structures (Extra States)

## Monotonic Queue Concepts

## DP in Intervals (Break on Boundaries)

## DP in Intervals (Extra States)

## DP in Intervals (Break in Middle)

## Sliding Window & Monotonic Queue

## Rolling Hash

## Combination & Permutation & DP Counting

## Monotonic Queue in DP

## Reduce Time Complexity in DP

## State Compression DP

## Built-in C++ String Functions

## Linear Recurrence Relation & Binary Exponentiation & DP Counting

## Hard-to-Detect DP

## Pure Greedy

## Binary Search the Result

## Palindrome & DP

## Merge Sort

## DP in Linear Structures & Real Result

## Divisors & Factors

## KMP

## Pure Bit Manipulation

## Monotonic Queue (Pure)

## Segment Tree

## DP in Intervals (Dynamic)

## Date

LeBlanc’s law: "Later equals never".

Read More

Read More

Read More

Read More

Read More

Read More

Read More

Read More

Read More

Read More

Posted on

Posted on

Range Update Index Update

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.

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.

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….

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…

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…

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….

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…

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: Edges are undirected or directed; Edges have positive or negative weights; No circles have negative weights; It is actually…

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.

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…

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…

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…

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…

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.

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.

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…

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…

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 …

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…

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…

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…

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…

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…

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…

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…

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…

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…

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….

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…

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…

Posted on

Summary In this post, I will introduce some common techniques related to divisors and factors. Details Number of Divisors GCD

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…

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…

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…

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…

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…

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