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.

Leave a Reply

Your email address will not be published. Required fields are marked *