F - Good Division Editorial by evima
Preparations
\(X\) is a good sequence if and only if:
- \(|X|\) is even, and no value occupies the majority of \(X\).
Proof
The necessity is clear. We will show sufficiency. Let $|X|=2n$. The case $n=1$ is clear. When $n\geq 2$, let $m$ be the mode of $X$. If $m \lt \frac{|X|}{2}$, there will never be a value that becomes the majority. If $m=\frac{|X|}{2}$, we need to erase $m$. If the mode is unique, let us erase $m$ and another value next to each other from some position. If there are two modes, $X$ consists of two different values, so let us erase those two values next to each other. Then, the case is reduced to the case of $n-1$, so the sufficiency in the general case is shown.Since \(|X|\) is even, let \(p_i = (x_i,y_i )= (a_{2i-1},a_{2i})\) and consider dividing \(p_1,p_2,\ldots,p_N\) into non-empty subsequences.
\(\mathrm{O}(N^2)\) solution
The following \(\mathrm{O}(N^2)\) solution leads to the final solution.
A contiguous subsequence \(p_i,\ldots,p_j\) is not good if and only if:
- there is an integer \(v(1 \leq v \leq 2N)\) that occupies the majority of \(p_i,\ldots,p_j\).
For each \(v\), let us associate the following value for \(i\): \(1\) if \(x_i=v\) and \(y_i=v\), \(-1\) if \(x_i \neq v\) and \(y_i \neq v\), and \(0\) if neither holds. Then, the condition for \(v\) is satisfied if and only if:
- the values for \(i,i+1,\ldots,j\) totals \(1\) or greater.
Let \(\mathrm{dp}_i\) be the number of divisions of \(p_1,\ldots,p_i\) into good sequences. Apply the inclusion-exclusion principle while maintaining the following values for each \(v\) to process the transitions in \(\mathrm{O}(N^2)\) time in total: the sum \(s\) of the values for \(1,2,\ldots,i\), the sum \(memo_i\) of \(\mathrm{dp_j}\) over all \(j\) such that the values for \(1,2,\ldots,j\) totals \(i\), and the sum of \(memo_j\) over all \(j\) such that \(s-j \gt 1\).
\(\mathrm{O}(N)\) solution
Consider finding for \(v\) the set of indices in the segments that \(v\) could occupy the majority of. We are particularly interested in whether there is a segment containing \(i\) such that the value for \(i\) is \(0\) or less where \(v\) is the majority.
If there is a segment containing \(i\) where \(v\) is the majority, at least one of the following holds.
- There is a segment \([l,i]\) whose value for \(l(\lt i)\) is \(1\) and whose sum of values is \(0\) or greater.
- There is a segment \([i,r]\) whose value for \(r(\gt i)\) is \(1\) and whose sum of values is \(0\) or greater.
Proof
It is not disadvantageous to erase segments that contain $0$ or $-1$ to the left (or right) of $j$, so we may assume that the elements at the ends are $1$. The maximum sum for the values in a segment containing $i$ can be computed as (the maximum value for $[l,i]$) $+$ (the maximum value for $[i,r]$) $-$ (the value for $i$). If the above conditions were not satisfied, this value would be negative, so there is no segment containing $i$ where $v$ is the majority.From this fact, one can find the maximum total value for \([l,j]\) for each \(j\) by appropriately handling \(v\) in ascending order of \(i\) such that \(p_i=(v,v)\). Similarly, one can find the maximum total value for \([j,r]\) for each \(j\) by handling \(v\) in descending order of \(i\).
Additionally, we can abort the process for the positions where the maximum value is negative. By considering the above process, the number of indices \(i\) that, although \(x_i \neq v\) and \(y_i \neq v\), can be in a segment where \(v\) is the majority is the number of indices \(j\) such that \(x_j = v\) and \(y_j = v\) multiplied by some constant factor, so there are \(\mathrm{O}(N)\) in total over all \(v\).
Therefore, one can find for each \(v\) some segments that correspond to sets of indices that can be in a segment where \(v\) is the majority, and apply the inclusion-exclusion principle as in the \(\mathrm{O}(N^2)\) solution to solve the problem in \(\mathrm{O}(N)\) time.
posted:
last update: