Learning notes on 2-SAT

Algorithm to solve 2-SAT

First decompose the implication graph into SCCs, and then if $x_i$ and $\neg x_i$ is in the same SCC, then the answer is impossible. Else it suffices to choose the variable that appears later in the topological order to be true.

Problems and Techniques

Enforcing one variable to be true: link
To do that, we can just add an edge from $\neg x_i$ to $x_i$

Enforcing at most one variable among several to be true
This can be done in $O(n)$. Order the nodes arbitrarily. Then we can build prefix nodes for each prefix part of the nodes and establish implication between those prefix nodes and the variables themselves.

Notes on Codeforces Problems: Rating 2400 (2)

Reduction to LIS: 76F
First, we need to understand the LIS problem with more depth. LIS problem, more generally, finds the longest sequence $X = [x_1, x_2,… , x_n]$ where $p(x_i) < p(x_{i+1})$ and $q(x_i) < q(x_{i+1})$ for $1 \leq i \leq n – 1$ for some function $p$ and $q$.
Then we return to the original problem to see how we can reduce it to LIS. After doing transformation to the formula, we see we can reach from $i$ to $j$ if and only if $|x_i – x_j| \leq (t_j – t_i) * V$. Then let $p_i = – x_i + t_i * V$ and $q_i = x_i + t_i * V$, then we can use LIS to solve this problem.

AC Automaton/ DP: 86C
AC Automaton is a good choice for maintaining “where we are when matching several strings”, but we also need to record how many characters are not matched yet when we are doing DP.
Another Note: To check whether a node is the end of a string, we need to check along the fail pointer until we reach the root.

Bottleneck Edge of Paths /Minimum Spanning Tree: 632F
The inequality in the problem looks like triangular inequality, which means we can somehow extend it into paths between two vertices, i.e. for any path between vertex $i$ and $j$, the maximum edge is large than the direct edge between them.
Then the way to solve this is to construct the MST and try to check each direct edge.

Euler’s Formula on Planar Graph: 933C
The solution of this problem utilizes Euler’s Formula, which relates the number of edges, vertices, and regions in a connected planar graph. $v-e+f = 2$, where $v$ is number of vertices, $e$ is number of edges, and $f$ is number of regions.

Reduction to MST / DP: 1120D
The first solution is to reduce this problem to MST. The idea of substituting between different tree nodes is similar to the way we make exchange argument in MST.
The second solution uses DP and the observation that we only need to care the cases where only one or zero vertice is left uncovered.

Almost Tree / Diameter: 835F
The graph is a almost tree, which contains a cycle and a bunch of trees attached to each node of the cycle. Ideally we want to enumerate the edge to delete. To do this, we can pick an arbitrary edge on the cycle, and do case analysis on whether it will be deleted. If yes, we can just run the diameter finding algorithm; If no, we can do some prefix/suffix sum around the cycle.

FFT / Segment Tree / Combinatorics: 1218E
1. While a good way to maintain single point/range update is to use a segment tree, it is still surprising to me that we can keep a frequency/sum list in each node and do convolution when merging nodes.
2. There is a step where we need to calculate array $s$ such that $$s_i = \sum_{j = 0}^{i} {{N – j}\choose{i – j}} \cdot t_j \cdot d^{i-j}$$. We can also use convolution to calculate this by spliting terms to those only related with $j$, $i – j$, $i$ respectively.
3. If we want to merge several intervals with complexity $O((n + m) \log (n + m))$. We can do this by pairing the smallest intervals together each time. This will yield a complexity of $L \log L$, where $L$ is the sum of all the intervals.

Segment Maintaining Max Prefix Sum: 1220F
We can keep the max prefix sums in a segment in two ways. One is using single point update and use a slightly more complicated merge function. Another is using lazy propagation directly on the prefix sum.

Divide-and-Conquer to Fit in Memory: 101E
If there is sufficient memory, we can do a straight-forward $O(n^2)$ DP. However, due to the tight memory constraint, in order to recover the answer, we will need to recursively find the middle point in the optimal answer using meet-in-the-middle tenique and divide the problems into the half, which yields a linear space complexity. In this way, the time complexity will be $O((n + m) ^ 2)$, which is still OK.

Reduction to Query in Segment Tree: 117D
One can see, when trying to caculate the sum, it is exactly like the process of querying sum in a segment tree.