Educational Codeforces Round 118
Educational Codeforces Round 118
D. MEX Sequences
A subsequence is valid if and only if one of the following is true for any prefix.
\(\{b_1, b_2\dots b_k\}=[0,k]\). (expandable)
\(\{b_1, b_2\dots b_k\}=[0,k]\cup\{k+2\}\). (non-expandable)
We can maintain the number of type 1/ type 2 subsequences with \(\mathrm MEX = k\), while adding \(a_i\) accordingly.
E. Crazy Robot
elementary BFS practice.
F. Tree Coloring
The objective is hard to achieve directly. We can apply Inclusion-Exclusion Principle to simplify the constrains.
Let \(f(n)\) be the number of coloring that has at least \(n\) edges with \(c_{fa} =c_v +1\).
Then \(Ans=\sum_{k}(-1)^kf(k)\).
\(f(n)\) can be calculated using divide-and-conquer FFT from the equation below.
\[ f(k)=(n-k)!\sum_{u_1,u_2\dots u_k\in V}\prod_{i=1}^k|childs(u_i)| \]
time: \(O(n\log^2n)\)
space: \(O(n)\)