HDU Multi-University Training 2019, Contest 3

Segment tree for optimizing DP: Problem B
First we can binary search on the answer, and then we consider a $O(n^2)$ DP where $dp[i]$ means the maximum number of partitions we can have ending at $i$th position. Then transition is as follows $$dp[i] = max_{j} (dp[j]) \text{ s.t. } sum[i] – sum[j] \leq val$$. Since the constraints is in a continuous range of prefix sum, we can keep them in a segment tree to do fast maximum queries.

Wilson’s Theorem: Problem F
For any prime $p$, we have $$(p – 1)! = -1 \text{ (mod } p)$$

HDU Multi-University Training 2019, Contest 2

Longest Increasing Subsequence Revisited: Problem B
An alternative way to solve LIS: Using a segment or BIT to keep the maximum length ending with number $i$. To choose the lexicographically smallest/largest, we can greedy pick the first/last available number.

Contribution Technique?: Problem F
The key thing to notice is the product of any two unit cube. No matter how we split the cubes, they always stays the same. That means the answer is always the same, which equals to the sum of products of all pairs of unit cube. We can calculate that with the help of FWT.

Tricky Build-up of min-cut graph: Problem H
Consider having two items $A, B$ in a min-cut graph and the source $S$ and the sink $T$. Consider 5 edges between those vertices: $SA, SB, AB, AT, BT$. We can set up the cost of those edges properly so that cutting in some edges corresponds the profit that we are not able to get by seperating them. There are 5 variables and 4 equations, so we can have some solutions. In the setting of the problem, we can always get a non-negative solution. Then we get add the graphs of two vertices up and get the final graph.

Palindrome Tree: Problem I
Using DFS/Binary Lifting on the fail tree, we can know if there is a suffix palindrome of certain length. Then can add them to the answer.

Learning notes on Palindrome Tree

Basic things this structure can do
1. the number of distinct palindrome substring in a string (which turns out to be the number of extra states, which is linear)
2. the number of times each palindrome appears
3. The number of palindromes (or sum of the corresponding properties) that ends in a certain location.
Properties
1. The size of the tree is $O(n)$. This is a result of the fact that at most one new distinct palindrome can be added when we add a new character. (Otherwise, choose the longest of them, $s_{longest}$, and the shorter one will definitely appear if we flip it from the middle point of $s_{longest}$.)
2. Each fail pointer is pointing to a smaller index. So when we want to do tree DP, we can just use the index as the topological order.
Other tricks:

Adding characters from both sides: HDU 5421
To do such thing, we can keep a extra pointer at the begining of the string. Both pointer will be the longest palindrome prefix/suffix. The operations will be symmetric, and, additionally, when the new distinct palindrome we get is the new whole string, we need to update both pointer to keep the property of the pointers.

To be continued…

Learning notes on Fast Bitwise Transform

FWT (Fast Walsh-Hadamard Transform) is a good tool to do fast bitwise convolution. For example, in xor operation, given sequence $A$ and $B$, we can calculate $C$ in $O(n \log n)$ such that $C[i] = \sum_{j \oplus k = i} A[j] \cdot B[k]$.

There are two main properties for the $FWT$ functions for different bitwise operations, where are pretty similar to FFT. The first one is that $FWT(C) = FWT(A) * FWT(B)$, where “$*$” is element-wise multiplication. The second is that there is also $UFWT$ which let us convert the sequence back.

Especially, for “or” operation, $FWT(A)[i] = \sum_{i | j = i} A[j]$, which essentially means the sum over all the subsets for $i$; for “and” operation, $FWT(A)[i] = \sum_{i \land j = i} A[j]$, i.e., sum over supersets.

Related Problems

Frequency Convolution: SRM518 Hard, HDU 5909, HDU 6596
This is the basic application for this transform. Sometimes we can also use fast exponentiation to speed up the same convolution.

Accelerating Brute Force: CF662C
We can see for each way of brute force as a convolution between the frequency and the minimum one we can have for certain number. Thus we can do a convolution for once and get the answer for all.

Making the problem easier: CF800D
If we are asked to solve a problem for some values $x$ and solving for the supersets of $x$ is easier, then we can solve the superset version and transform it back to the exact value version.

HDU Multi-University Training 2019, Contest 1

Dynamic Programming: Problem A
Since there can only be four numbers, we can do a four-dimensional DP to record the last occurrences of the numbers. The time complexity is $O(n^4)$. One dimension can be used to record the current number, so we can reduce it to $O(n^3)$ space to fit into the space.

XOR Basis: Problem B
This can be solved by segment tree in $O(n \log n \log A)$, but this is too slow. Instead, we can keep a upper-triangular basis for each right bound. We should put the number with higher index as high as possible and put other numbers down. In this way, when we are querying the maximum for range $[l, r]$, we take the number in the “$r$ basis” when it is in the bound ($l_i \geq l$), and it can be guaranteed that every number we take is valid, i.e. can be expressed as a linear combination of the number in $[l_i, l]$.

Sliding Windows for String Matching on SAM: Problem F
There are several things to notice: The first is that the range for possible transition for copying text is increasing, which means we can use a deque to maintain the minimum. Furthermore, since we can prove the DP value is non-decreasing, we can just choose the smallest position to do the copy. To find that position $j$, we maintain a SAM for $s[1;j-1]$ and keeping adding $s[j]$ into the SAM until we can find $s[j;i]$ in $s[1;j-1]$. We use a pointer $pt$ to record the current matching. To delete a character, we just keep moving $pt$ until $curlen \leq st[pt].len$.

Generating Function/ Convolution: Problem L
Write the operation as generating function, we have $$\sum_i b_i x^i = (\sum_i a_i x^i) (\sum_i x^{ik})$$, which tells us that the order of operations does not matter. We also see that the operation of the same kind can be combined together by using the fact that the coefficient of $x^t$ in $(\sum_i x^{i}) ^ l$ is ${t + l – 1}\choose{l – 1}$. Then we can use three NTTs to get the answer.

Prüfer Code, Cayley’s Formula, etc

Prufer Code is a way to represent a labeled tree as an array, which is related some tree counting problems

The Prüfer code is a way of encoding a labeled tree with $n$ vertices using a sequence of $n-2$ integers in the interval $[0, n−1]$

Conversion and Bijection between Tree and Prüfer code

We can construct Prüfer Code from a given tree by removing the smallest leaf and add the number of the only vertex adjacent to it to the list until there are only two vertices.

We can also constructing a tree from a given Prüfer Code by the following procedure.
for i from 1 to n – 2:
Let the smallest leaf not in the current sequence and not used be u
Let the first element in the sequence be v;
Mark v as used;
Connect u and v;
Delete the first element in the sequence;
endfor
Connect the last two unused vertices;

From the construction, we know each Prüfer Code has a tree, and each tree has a Prüfer Code. Let $f: \text{Tree} \rightarrow \text{Prüfer Code}$ be the function we use to convert a tree to a Prüfer Code. We can further prove $f^{-1}(f(t)) = t$ for any tree $t$ by induction, which implies that there is a bijection between labeled trees with $n$ vertices and Prüfer Code with length $n – 2$. The direct result of the bijection is Cayley’s Formula as shown below.

Cayley’s Formula and Generalized Version

Theorem 1 (Cayley’s Formula): For any integer $n > 0$, the number of trees of $n$ labeled vertices is $n^{n-2}$.

Theorem 2 (Generalized Cayley’s Formula): Let $T_{n, k}$ be the number of labelled forests on $n$ vertices with $k$ connected components, such that vertices $1, 2, …, k$ all belong to different connected components. Then $T_{n, k} = k n^{n-k-1}$.

Property of Prüfer Code

1. The vertex with the highest number will not be in the Code
2. Each vertex $i$ appears $d_i – 1$ times in the Code, where $d_i$ is the degree of vertex $i$.

Lemma 3: Given the degree of each vertex in a tree of size $n$, $d_1, d_2, …, d_n$, the number of possible trees is $$\frac{(n – 2)!}{(d_1 – 1)! (d_2 – 1)! … (d_n – 1)!}$$

Related Problems

Prüfer-Code-like Bijection: CF156D
Problem in short: Given a graph, find the number of ways to connect the graph with minimum edges.
Idea: We can construct sequence $P$ and $Q$ that represent the final graph similar to Prüfer Code. Let $k$ be the current number of connected component. $P$ denotes the vertex $v$ that we connect to when we remove the smallest labeled leaf component $C$ one by one. $Q$ denotes the vertex in $C$ that we use to connect $v$. The bijection between the sequences can be proved in a similar manner. Since for each sequence $P$, we will have $\prod_i sz_i$ different $Q$s, where $sz_i$ is the size of the $i$th component, the answer will be $$n^{k-2} \cdot \prod_i sz_i$$.

Generalized Cayley’s Formula: CF1109D
Trivial Application

Some Properties
• Each state in the SAM corresponds an equivalent class of substrings of $s$ which appear in the same set of positions.
• For some state $v$, $len(v) – minlen(v) + 1$ is the number of distinct substring in the corresponding class.

To check if $t$ occurs in $s$, we can keep matching $t$ on the SAM of $s$, go to the next state if the current character is matched, or get through suffix link otherwise.

If we want to know how much a string $t$ can be matched for each state in the SAM of $s$, we can first keep matching it and record whenever the character is matched, and then we can propagate the value through the links.

Fact: Every distinct path from the root is a distinct substring.

Following from this fact, we can use DP to calculate lots of things, such as number of distinct substrings, sum of distinct integers.
Example: sum of dictinct integers, Morse Code

The suffix links forms a tree in which you can propagate information upwards, like the first/last ocurring positions, number of characters matched in a suffix, etc.
Example: propagation of available indices

Related Problems

Sliding Windows for String Matching: HDU 6583
Analysis in the blog for the original contest.

Notes on Codeforces Problems: Rating 2300

This post is used to record my notes on some of the problems (Mainly for difficulty 2300) in Codeforces

126D Canonical Decompositon into Fibonacci number: Link
We need to use a so-called “canonical” way to represent the decomposition of fibonacci number, and do DP on that representation. “You can imagine Fibonacci coding by following way: i-th bit of number corresponds to the i-th Fibonacci number. For example, 16=13+3 will be written as 100100. You can represent into this code any positive integer, for that no two neighbouring 1-bit will be present.”

690C3 Diameter of the tree: Link
Keeping the diameter of the tree online. “keep a pair of vertices (u, v)” and compare (u, w), (v, w), (u, v) when w is added.  Pretty nice property of diameter!

1149C Between tree diameter and bracket sequence: Link
This problem needs us to exploit the property of tree diameter/LCA in bracket sequences, which is pretty similar to a solution to solve the unweighted version of QTREE4 in SPOJ. The two solutions uses different interesting observations to convert it into something solvable by the segment.
1. The LCA of two nodes is essentially the shallowest point between those two nodes in the bracket sequences.
2. Or you can take the substring between the two nodes, for example, “] [ [ ] [ ] ] ] [ ] [ [” , and you take away all of the matched parenthesis between them. It becomes “] ] [ [“, which is essentially the same as the path from one node to the other “]” means going up, and “[” means going down.)
or either of those two ways, we can use a segment tree to maintain the information in the bracket sequence.

228C Fractal Structure and Sparse Table: Link
While rolling hash yields a valid solution for this problem, the one used by the tutorial is more elegant. Fractal is actually a good place to reduce the structure into sub-structure. We can use the doubling technique (like in suffix array construction/ sparse table construction) and use dynamic programming to solve it.

While the problem here is solvable with standard divide and conquer, we can just do a smart brute force to pass by enumerating every maximum number and choose the smaller side to iterate. The complexity analysis is pretty similar to that of divide and conquer (smaller to large): “Every element will be processed no more than logn times because, if we process it in a segment of size m, the smaller part of it contains no more than m/2 elements (which we will process later, and the smaller part of this segment contains no more than m/4 elements, and so on).”

Bitmask DP here. The DP dp[mask] can be define as “the prefix of elements we have made so far”, and we can get a $O(3^n + n \cdot 2^n)$. We can additionally record how much we have covered for the next element, and then we can have a $O(n \cdot 2^n)$ solution.

718C Query on Fibonacci Sum: Link
Classic problem. There are two ways of solving this problem (both using lazy propagation in the segment tree):
1. Using the explicit formula of n-th Fibonacci number, the updating is just range mulplication. In this way, we need to use fast exponentiation.
2. There is another way. Recall that we can get the $n$-th Fibonacci number by matrix multiplication and we can keep a 1 by 2 matrix in each node and use matrix exponentiation to maintain the matrix.
Both of the ways have a complexity of $O(n \log^2{n})$

The most important thing for this problem is realizing that at most one of the three inequality of a triangle can be violated at the same time. That means we can count all the possibilities and substract the violating ones from that.

The key part to figure out for this problem is to see how we can do efficient updates from one level to another. While the solution used some “square root” optimization method, we can also take advantage of the property of Manhattan Distance by (spliting into 4 case and) using some 2D segment tree or just collecting the maximum for each row.

246E DSU on tree / query on DFS order: Link
There are two different solutions: one with range queries in the dfs order, another with DSU on tree. The DSU solution is involved with keeping the (depth, set of integers) pairs in each vertex. That can be done by using a deque of sets since in this way we can easily append the new depth level in the front when we move into a new vertex.

For the same kind of souvenirs, we always take the most expensive ones of them. Then we can see the cost function with the number of pieces taken is convex. However, it is noteworthy that when we do ternary search, the function of weight-2 items are not convex if we are using the amount of space left as the input, (the amount of space has a step size of 1 and the weight-2 items has a step size of 2.)

756C Looking from backward? / Balance Value: Link
The key observation of this problem is that we should look at the operation from backwards and calculate the so-called “balanced value” of each operation. It turns out that the element on the top of the stack is the first element (from backwards) that is larger than zero.

Unusual solution, which is pretty similar to hill climbing: Start a arbitrary solution to turn things around. It turns out it will ultimately “converge” (i.e, become a valid answer).

593D Jumping using union find: Link
Basic observation: 1. the order of the division doesn’t matter. 2. every number larger than 2 divides the number into halves or less. Then we can skip those “one”s by using a technique like union find.

Notes on Codeforces Problems: Rating 2400 (1)

Currently I am solving Codeforces problems with difficulty 2400. This post is to record some new/fancy ideas to solve the problems.

Linearity of Expectation: 280C
Calculate the contribution of each vertex being directly deleted, which is $\frac{1}{depth(v) + 1}$, and sum them up.

DFS Spanning Tree / Edge 2-connected Component: 732F
The key idea of this problem is directing edges in a 2-connected Component into a strongly connected component. The idea is pretty simple: Do a DFS and add the edge along the way. The correctness can be proved using the DFS spanning tree: We can always go back through the back-edges, otherwise there will be a bridge.

Change the problem! / DFS Spanning Tree: 405E
There is a better way to interpret this problem: directing edges so that the every vertex’s in-degree becomes even. Then the problem becomes more free and we can use arbitrarily assigning directions to edges not in the spanning tree and then assign others according to the parities.
Note: The DFS spanning tree has both “forward edges” and “backward edges” to the visited edges.

Complexity Analysis: 850C
While the solution for this problem is brute-forcely calculating the SG function, it is tricky to prove it will work in time. The analysis goes as follows: For a certain mask with length $k$, the number of masks with highest bit $m$ it goes through during DFS can be limited. If $1 \leq m \leq k / 2$, then there can be at most $2^m$ masks. If $k / 2 \leq m \leq k$, there can be at most $2^{k – m}$ masks since only the first $k – m$ bits can change.

Merging Tries: 601D
The amotized complexity for merging a trie (in this problem) is, surprisingly, linear, if we merge it smartly: Suppose we are merging trie $A$ to tree $B$. Keep descending along two tries and stop whenever one tree has not children. If it is $B$, then it is fine. If it is $A$, then we “clip” the subtree (instead of visiting all of them) and add it into $B$. In this way, every trie node will be visited exactly once when it is merged into other nodes.

Multiplicative Function: 757E, 1097D
The key part of both of the two problems are seeing that the function asked is a mulplicative function. Then, we can calculate the answer for each prime divisors and then multiply them to get the final answer.
A useful lemma: A function $$f(n) = \sum_{d | n} g(d)$$ is multiplicative if $g$ is multiplicative.

While the intuition is that we will most likely choose numbers as large as possible, we can prove that we will either choose the largest numbers one by one or choose $max / 2$, $max / 3$, $max / 5$.

Connected Component on 2D Plane/ Combinatorics: 870E
1. When we build the graph such that each point is connected to the neighboring points in all four directions, we can get a graph with a nice property: Every leaf has its unique x-value/y-value in the connected component.
2. Another Key point of this problem is to think about what kind of configuration cannot be in the result. (Or intuitively realize that almost all the configurations are possible.)

Knapsack with Huge Amount of Small Values: 1132E
We can see that if we choose lots of items with some weight, we can group them together to a block of size $S$, where $S$ is LCM of $1$ to $8$. Then we can do a DP with the remaining items.

Knapsack with Few Categories of Same Values: 95E
The first observation is that there can be at most $O(\sqrt n)$ different sizes of component. We should notice this especially when we can solve the problems of the same size efficienctly. (Another example: 666C)
Then we can use the following way to solve the knapsack problem of same values: represent the number of items $C_i$ into $2 ^ 0 + 2 ^ 1 + …$ that we can separate them into $O(\log C_i)$ items and do the classic knapsack problem one by one.

Centroid Decomposition: 914E
By centroid decomposition, we can take all the paths into consideration. Note that when counting for a certain node, we can propagate the value into its parent.

Mincost-Maxflow: 277E, 863F
When a problem includes different variables constraining each other and requires finding the minimum cost, we should think about mincost-maxflow.

Divide-and-Conquer/ Persistent Segment Tree/ Randomization: 840D
Three are three practical ways to solve this problem:
1. Divide-and-Conquer. If we apply D&C, we can see that each of the $k$ most frequent values in a query that goes across the mid point must be one of the $k$ most frequent in $[L, mid]$ or $[mid+1, R]$.
2. Persistent Segment Tree: Keep the a tree of frequency and the maximum. We can answer each query in $O(k \log n)$
3. Since we try to find some element that appears a lot of time in a range, we can have several random picks in the array. Then with high probability, the intended element will be found.

Reduction to finding a point covered by largest number of rectangles: 377D
The key approach to think about the solution is to think $(L, R)$ as a point in the 2D-plane. Then we can reduce this problem to a classic one.

Probability/ Two pointers: 1194F
We deduce the expectation by thinking about how each crossword can contribute to the answer: $P(i) = \frac{1}{2^i}\sum\limits_{k = 0}^{m_i}{\binom{i}{k}}$
Then the key observation is that we can transform from $(i, m_i)$ to the neighboring pairs efficiently by using: $2 \cdot \sum\limits_{k = 0}^{x}{\binom{n}{k}} + \binom{n}{x + 1} = \sum\limits_{k = 0}^{x + 1}{\binom{n + 1}{k}}$, which essentially somes from Pascal Triangle Formula $\binom{n}{k} + \binom{n}{k + 1} = \binom{n + 1}{k + 1}$

Sweeping Line: 1194E
Note: While the limit for $n$ is 5000, since the set of segments will be splited into vertical and horizontal ones, $O(n^2 \log n)$ solutions will work fine.
For sweeping line, putting things in a certain order can be very important.

First we can see that if the adjacency lists of two vertices are the same, then we can always assign the same value to them and merge them together. In the compressed graph we know that if a the degree of vertex is $\geq 3$, there will be no answer based on the fact that the vertices with different adjacency list must have different number.
Useful fact: Any path between two vertices can be expressed as: “xor-sum of edge on any path” $\oplus$ “an element in the cycle space of the graph”.
Both with $O(n)$ preprocessing, while Z-function can check the cycle in the string in $O(n)$, the prefix function can do that in $O(1)$, which is crucial for this problem.
Define $dp[i]$ as the maximum profit we can get ending at $i$ (only considering the segment ending at or before $i$). Then we have $dp[i] = max_{j} (dp[j] + p[j + 1, i] – cost[j + 1, i])$ since the solution will look at several consecutive segment. Then we can move from left and keep the values in a segment tree and add value into a range when we have a new segment.