Codeforces Round #738 (Div. 2)
Codeforces Round #738 (Div. 2)
statistics: problem solved: 4/6 realtime, 1 after contest.
C - Mocha and Hiking
This problem is a partial proof that
There always exists an Hamiltonian path in a tournament graph.
D2. Mocha and Diana (Hard Version)
Approach: greedy graph matching technique.
First, try add all possible edge \((1, u)\)
Then all nodes which are not in the same component as node 1 must be in the same component with node 1 in the second graph.
Now we will consider nodes of two types, the ones that are in the same component than 1 in the first tree, and the ones that are in the same component than 1 in the second tree. We will store all nodes of type 1 in a stack p1, and all nodes of type 2 in a stack p2, and we will try to match them with the following algorithm.
If the top of p1 is in the same component than 1 in both trees, delete it
If the top of p2 is in the same component than 1 in both trees, delete it
Otherwise, add an edge between the top of p1 and the top of p2.
E. Mocha and Stars
Approach: Mobius Inversion (the good old gcd inversion)
\[ \begin{aligned} Ans=& \sum_{l_i \le a_i \le r_i}[\sum a_i \le m][gcd(a_i) = 1]\\ =& \sum_d \mu(d)\sum_{l_i \le a_i \le r_i}[\sum a_i \le m][a_i|d]\\ =& \sum_d \mu(d) \sum_{\lceil\frac{l_i}{d} \rceil \le a_i \le \lfloor \frac{r_i}{d}\rfloor}[\sum a_i \le \lfloor\frac{m}{d}\rfloor]\\ \end{aligned} \]
the rest part is just some \([z^k]\frac{1}{(1 - z)^{n + 1}}\prod(1-z^{k_i})\), which can be solved \(O(nk)\) through DP
Total time complexity:\(O(nm\ln m)\)