**Matroid Intersection**: 1284G

The problem asks us to find a spanning tree where certian nodes cannot be leaves. The key thing to think about is “What does it mean to be non-leaves?”, and the idea is that the total degree of a node is at least 2. Therefore, we can try to find an acyclic edge set where the degree of each special node is exactly 2. This can be done using intersection of a graphic matroid and a colorful matroid (We restrict each color to have at most two instances, and check whether it is exactly 2 in the final maximum independent set).

# Tag: Codeforces

## CF Problems: 2020 Mar. ~ Apr.

Problems are sorted from most recent to least recent

**FFT, String Matching**: 1334G

When we want to matching two string with more flexible criterion, we can try to come up with some formula $f$ for comparing two character where $f(u, v) = 0$ only when $u = v$. In this case, $(s – t)^2 (s’ – t)^2$ can be a good choice. After expanding the equation, we only need 3 FFTs to get the answer.

**Bitmask, SOS DP, Brute Force**: 1326F2

There are several techniques that we could use in this kind of problems: DP over subset/superset. Usually we can solve the “superset” version of a problem easier than itself. Like in this case, if we only care about the string location that must be 1, we only need to care about each component.

Then we can realize the split of the component (i.e. the partition of the sequence) can be at most as $P(18) = 385$ (recall NAC20J, which uses P(30) = 5040), and each split, no matter how ordered, has the same number ways to achieve. Then we can solve for each configuration and merge them together.

To merge them, we can use subset transformation (subset transform is for “OR”, superset transform is for “AND”) to make it easier to unite different component in a partition. When we get the answer, we can transform the result back from “superset” version.

One side note on the easier subtask is that it used the fact that $\sum_{k = 0}^{n} {{n}\choose{k}} 2^k = 3^k$ by binomial theorem. so we can do bitmask DP using two dimensional DP (one on the submask of permutation and another on the submask of string), which is $O(3^k k /2)$.

## Problems Notes on Codeforces String Problems

~~My goal is to solve all the problems related to strings/hashing/suffix structure starting from rating 2600 in Codeforces~~. I will keep summarizing problem ideas here.

If a problems falls into a specific large category, I will summarize it in those independent blogs:

Palindrome Tree

Suffix Automaton

Hashing

**Shortest/Longest Path Cut Vertex Checking**: 1214D, 650D, MCPC19B

Sometimes, if we want to check if a vertex is neccesary for a shortest path/longest path, one way to do is hashing as mentioned in the hashing blog. Another much easier way is to group the vertices by distance. The vertex is the cut vertex if and only if it is the only one in that “distance level”.

**Non-Palindrome Cutting**: Timus 2057

Consider that the only “impossible” cases are like $aaaaa$, $aaaabaaaa$, or $abababa$ (not really sure how to prove, though).

Otherwise the minimum answer is either $1$ or $2$. Check it brute-forcely.

For the maximum answer, we have $dp[i] = max\{dp[j] + 1\}$ for all $j$ s.t. $s[j + 1, i]$ is possible to split. Then we do the dp transition by excluding the three impossible cases.

Reference:

1. URAL Palindromic Contest (in Chinese)

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

1156E **Taking Advantage of Recursion Tree**: Link

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).”*

71E **Bitmask DP**: Link

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})$

571A **Combinatorics**: Link

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.

667D **Manhattan Distance**: Link

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.

808E **Convex Function**: Link

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.

272E **Hill Climbing?**: Link

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.

**About Number Division**: 1183F

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.

**Adjacency List**: 794D

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.

**“Path Space” under XOR operation in a graph**: 845G, 724G

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

**String Cycle Checking**: 825F

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.

**Segment Tree and DP**: 115E

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.