↵
↵
<spoiler summary="New Year and Naming">↵
[tutorial:1284A]↵
Writer: [user:ko_osaga,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203276)↵
</spoiler>↵
↵
<spoiler summary="New Year and Ascent Sequence">↵
[tutorial:1284B]↵
Writer: [user:ko_osaga,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203332)↵
</spoiler>↵
↵
<spoiler summary="New Year and Permutation">↵
[tutorial:1284C]↵
Writer: [user:ko_osaga,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203721)↵
</spoiler>↵
↵
<spoiler summary="New Year and Conference">↵
[tutorial:1284D]↵
Writer: [user:nong,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203704)↵
</spoiler>↵
↵
<spoiler summary="New Year and Castle Construction">↵
[tutorial:1284E]↵
Writer: [user:ckw1140,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203754)↵
↵
**Challenge:** Find $x_5$ in $O(n^2 \log n)$.↵
</spoiler>↵
↵
<spoiler summary="New Year and Social Network">↵
This problem can be cracked in polynomial time with various approaches. I'll introduce a few of them.↵
↵
#### $O(n^3)$↵
↵
As stated in the problem, this problem is a straightforward bipartite matching problem. With a simple DFS or union-find, you can construct a bipartite graph in the statement, and use well-known maximum matching algorithm. ↵
↵
#### $O(n^{1.5}\log n)$↵
↵
By using a similar solution to [Codeforces 786E: ALT](https://codeforces.me/problemset/problem/786/E), you can reduce the time complexity to $O(n^{1.5}\log n)$. The author didn't manage to squeeze this approach in time.↵
↵
#### $O(n^2)$: ↵
↵
By looking at the sample, it seems that $m = n-1$ always holds for some reason. In other words, the given graph always has a perfect matching. It turns out that this guess is true. Let's try to prove it using induction. ↵
↵
#### Inductive Proof. Attempt 1↵
↵
We induct on the quantity $|E(T_1) - E(T_2)|$. If the quantity is zero, then we can find an obvious bijection. Otherwise, we can find some edge $e \in E(T_1) - E(T_2)$. Since our goal is to reduce the difference, it would be reasonable to replace this edge to some other edge $f \in E(T_2) - E(T_1)$. Hopefully, we can show the following:↵
↵
**Lemma 1.** For any $e \in E(T_1) - E(T_2)$, there exists some edge $f \in E(T_2) - E(T_1)$ such that $T_1 - \{e\} + \{f\}$ is a tree.↵
↵
**Proof.** $T_1 - \{e\}$ have two components. If there exists an edge $f$ that connects these two parts, we are done. Otherwise, $T_2$ has no edges connecting these parts, finding a cut.↵
↵
Then, we can simply add the bijection $\{e \rightarrow f\}$, replace the edge $e$ with $f$ in $T_1$, and continue. Right? Sadly, this is wrong as it is changing the tree $T_1$. Although we found the pair of tree $(T_1 - \{e\} + \{f\}, T_2)$ with less value $|E(T_1) - E(T_2)|$, finding a bijection over $T_1 - \{e\} + \{f\}$ to $T_2$ is a different story, thus the proof fails.↵
↵
#### Inductive Proof. Attempt 2↵
↵
It would be good to make $T_1$ static, since otherwise our induction will fail. Then, what about repeating induction over $(T_1, T_2 + \{e\} - \{f\})$? Everything is good, but then we should also guarantee $T_2 + \{e\} - \{f\}$ is a tree. Is it possible?↵
↵
**Lemma 2.** For any $e \in E(T_1) - E(T_2)$, there exists some edge $f \in E(T_2) - E(T_1)$ such that $T_1 - \{e\} + \{f\}$ and $T_2 + \{e\} - \{f\}$ is a tree.↵
↵
**Proof.** $T_2 + \{e\}$ has exactly one cycle $C$. Since $T_2 + \{e\} - \{f\}$ should remain acyclic, $f \in C$ should hold. The cycle consists of edge $e$ and path from $T_2$, we should find such $f$ from the path in $T_2$, such that its endpoint connects two different component of $T_1 - \{e\}$. Label the vertices in the path by its component membership of $T_1 - \{e\}$. Since $e$ itself connects the different component, there should exist a edge in the path, which connects different component. Take it.↵
↵
Now, as $T_1 - \{e\} + \{f\}, T_2 - \{f\} + \{e\}$ is both acyclic, we can create the bijection $\{e \rightarrow f\}$, and also take $(T_1, T_2 - \{f\} + \{e\})$ for the induction stage. This proof also gives a straightforward $O(n^2)$ algorithm for finding the answer.↵
↵
#### $O(n\log n)$↵
↵
When we fix $e \in E(T_1) - E(T_2)$, finding the component where each vertices lie is easy: This can be done by preprocessing $T_1$ with a single depth-first search. Using this to find the $f$ is a different story: We have dynamically changing tree of $T_2$, which is hard to maintain.↵
↵
On the other hand, since Lemma 2 is symmetric, we can rather fix $f \in E(T_2) - E(T_1)$ and find $e$ instead. In this case, if we can know which subtree that a vertex belongs for $T_2 - \{f\}$:↵
↵
* If $f = \{u, v\}$, find the path between $u \rightarrow v$ in $T_1$↵
* If $LCA(u, v)$ belongs to same component in $u$, then find $f$ in path $v \rightarrow LCA(u, v)$. Otherwise, find $f$ in path $u \rightarrow LCA(u, v)$.↵
* Now, you can find $e$ using binary search on paths, which can be implemented with binary lifting↵
↵
Since $T_1$ is static, we can afford all these operation in $O(n \log n)$ time preprocessing. Now the point is to maintain $T_2$ to support subtree membership query. This can be done straightforwardly using Link-Cut tree or Euler Tour tree using $O(\log n)$ query time, which results in $O(n\log^2 n)$ time, but this is too slow (at least for us) to pass.↵
↵
Now from this point, we will assume $E(T_1) \cap E(T_2) = \emptyset$. We have a freedom over choosing $f$, so let's choose the $f$ as the edge connecting the leaf. The good property of leaf is that the subtree membership query is very easy: You can simply compare the vertex number. So, if we choose such $f$, we can find $e$ easily.↵
↵
What about changing the tree $T_2$ to $T_2 - \{f\} + \{e\}$ ? Note that, After $T_2$ becomes $T_2 - \{f\} + \{e\}$, we don't have to care about $e$ because it's in the intersection of $T_1$ and $T_2$. We can think about **contracting** the edge $e$: After adding an edge $e$ we can not delete, so in the component point of view, they are always in the same component: So we can remove the leaf edge $f$, and contract the ends of $e$. For the data structure to maintain these components, we can use Union-Find.↵
↵
Writer: [user:ko_osaga,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203787)↵
↵
**Challenge:** Lemma 2 works for the general matroid base set. So for any pair matroid base set from same ground set, perfect matching existsfor all base sets of matroidsin the exchange graph. Prove it.↵
</spoiler>↵
↵
<spoiler summary="Seollal">↵
[tutorial:1284G]↵
Writer: [user:ko_osaga,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203817)↵
↵
**Trivia 1:** This problem's working name was "yet-another-nowruz". You may want to compare the statement of this problem and IOI 2017 Nowruz ;)↵
↵
**Trivia 2:** Huge applause to [user:kriii,2020-01-05] who created amazing tests to break random solutions of G. We were very afraid of random solutions because of the huge difficulty gap between ABCDE/FG. Hopefully, the first 80 tests were good enough for the contest. But that's not the end of the story: we have 140 tests ;)↵
</spoiler>↵
↵
↵
<spoiler summary="New Year and Naming">↵
[tutorial:1284A]↵
Writer: [user:ko_osaga,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203276)↵
</spoiler>↵
↵
<spoiler summary="New Year and Ascent Sequence">↵
[tutorial:1284B]↵
Writer: [user:ko_osaga,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203332)↵
</spoiler>↵
↵
<spoiler summary="New Year and Permutation">↵
[tutorial:1284C]↵
Writer: [user:ko_osaga,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203721)↵
</spoiler>↵
↵
<spoiler summary="New Year and Conference">↵
[tutorial:1284D]↵
Writer: [user:nong,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203704)↵
</spoiler>↵
↵
<spoiler summary="New Year and Castle Construction">↵
[tutorial:1284E]↵
Writer: [user:ckw1140,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203754)↵
↵
**Challenge:** Find $x_5$ in $O(n^2 \log n)$.↵
</spoiler>↵
↵
<spoiler summary="New Year and Social Network">↵
This problem can be cracked in polynomial time with various approaches. I'll introduce a few of them.↵
↵
#### $O(n^3)$↵
↵
As stated in the problem, this problem is a straightforward bipartite matching problem. With a simple DFS or union-find, you can construct a bipartite graph in the statement, and use well-known maximum matching algorithm. ↵
↵
#### $O(n^{1.5}\log n)$↵
↵
By using a similar solution to [Codeforces 786E: ALT](https://codeforces.me/problemset/problem/786/E), you can reduce the time complexity to $O(n^{1.5}\log n)$. The author didn't manage to squeeze this approach in time.↵
↵
#### $O(n^2)$: ↵
↵
By looking at the sample, it seems that $m = n-1$ always holds for some reason. In other words, the given graph always has a perfect matching. It turns out that this guess is true. Let's try to prove it using induction. ↵
↵
#### Inductive Proof. Attempt 1↵
↵
We induct on the quantity $|E(T_1) - E(T_2)|$. If the quantity is zero, then we can find an obvious bijection. Otherwise, we can find some edge $e \in E(T_1) - E(T_2)$. Since our goal is to reduce the difference, it would be reasonable to replace this edge to some other edge $f \in E(T_2) - E(T_1)$. Hopefully, we can show the following:↵
↵
**Lemma 1.** For any $e \in E(T_1) - E(T_2)$, there exists some edge $f \in E(T_2) - E(T_1)$ such that $T_1 - \{e\} + \{f\}$ is a tree.↵
↵
**Proof.** $T_1 - \{e\}$ have two components. If there exists an edge $f$ that connects these two parts, we are done. Otherwise, $T_2$ has no edges connecting these parts, finding a cut.↵
↵
Then, we can simply add the bijection $\{e \rightarrow f\}$, replace the edge $e$ with $f$ in $T_1$, and continue. Right? Sadly, this is wrong as it is changing the tree $T_1$. Although we found the pair of tree $(T_1 - \{e\} + \{f\}, T_2)$ with less value $|E(T_1) - E(T_2)|$, finding a bijection over $T_1 - \{e\} + \{f\}$ to $T_2$ is a different story, thus the proof fails.↵
↵
#### Inductive Proof. Attempt 2↵
↵
It would be good to make $T_1$ static, since otherwise our induction will fail. Then, what about repeating induction over $(T_1, T_2 + \{e\} - \{f\})$? Everything is good, but then we should also guarantee $T_2 + \{e\} - \{f\}$ is a tree. Is it possible?↵
↵
**Lemma 2.** For any $e \in E(T_1) - E(T_2)$, there exists some edge $f \in E(T_2) - E(T_1)$ such that $T_1 - \{e\} + \{f\}$ and $T_2 + \{e\} - \{f\}$ is a tree.↵
↵
**Proof.** $T_2 + \{e\}$ has exactly one cycle $C$. Since $T_2 + \{e\} - \{f\}$ should remain acyclic, $f \in C$ should hold. The cycle consists of edge $e$ and path from $T_2$, we should find such $f$ from the path in $T_2$, such that its endpoint connects two different component of $T_1 - \{e\}$. Label the vertices in the path by its component membership of $T_1 - \{e\}$. Since $e$ itself connects the different component, there should exist a edge in the path, which connects different component. Take it.↵
↵
Now, as $T_1 - \{e\} + \{f\}, T_2 - \{f\} + \{e\}$ is both acyclic, we can create the bijection $\{e \rightarrow f\}$, and also take $(T_1, T_2 - \{f\} + \{e\})$ for the induction stage. This proof also gives a straightforward $O(n^2)$ algorithm for finding the answer.↵
↵
#### $O(n\log n)$↵
↵
When we fix $e \in E(T_1) - E(T_2)$, finding the component where each vertices lie is easy: This can be done by preprocessing $T_1$ with a single depth-first search. Using this to find the $f$ is a different story: We have dynamically changing tree of $T_2$, which is hard to maintain.↵
↵
On the other hand, since Lemma 2 is symmetric, we can rather fix $f \in E(T_2) - E(T_1)$ and find $e$ instead. In this case, if we can know which subtree that a vertex belongs for $T_2 - \{f\}$:↵
↵
* If $f = \{u, v\}$, find the path between $u \rightarrow v$ in $T_1$↵
* If $LCA(u, v)$ belongs to same component in $u$, then find $f$ in path $v \rightarrow LCA(u, v)$. Otherwise, find $f$ in path $u \rightarrow LCA(u, v)$.↵
* Now, you can find $e$ using binary search on paths, which can be implemented with binary lifting↵
↵
Since $T_1$ is static, we can afford all these operation in $O(n \log n)$ time preprocessing. Now the point is to maintain $T_2$ to support subtree membership query. This can be done straightforwardly using Link-Cut tree or Euler Tour tree using $O(\log n)$ query time, which results in $O(n\log^2 n)$ time, but this is too slow (at least for us) to pass.↵
↵
Now from this point, we will assume $E(T_1) \cap E(T_2) = \emptyset$. We have a freedom over choosing $f$, so let's choose the $f$ as the edge connecting the leaf. The good property of leaf is that the subtree membership query is very easy: You can simply compare the vertex number. So, if we choose such $f$, we can find $e$ easily.↵
↵
What about changing the tree $T_2$ to $T_2 - \{f\} + \{e\}$ ? Note that, After $T_2$ becomes $T_2 - \{f\} + \{e\}$, we don't have to care about $e$ because it's in the intersection of $T_1$ and $T_2$. We can think about **contracting** the edge $e$: After adding an edge $e$ we can not delete, so in the component point of view, they are always in the same component: So we can remove the leaf edge $f$, and contract the ends of $e$. For the data structure to maintain these components, we can use Union-Find.↵
↵
Writer: [user:ko_osaga,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203787)↵
↵
**Challenge:** Lemma 2 works for the general matroid base set. So for any pair matroid base set from same ground set, perfect matching exists
</spoiler>↵
↵
<spoiler summary="Seollal">↵
[tutorial:1284G]↵
Writer: [user:ko_osaga,2020-01-04]↵
↵
[Solution code](https://codeforces.me/contest/1284/submission/68203817)↵
↵
**Trivia 1:** This problem's working name was "yet-another-nowruz". You may want to compare the statement of this problem and IOI 2017 Nowruz ;)↵
↵
**Trivia 2:** Huge applause to [user:kriii,2020-01-05] who created amazing tests to break random solutions of G. We were very afraid of random solutions because of the huge difficulty gap between ABCDE/FG. Hopefully, the first 80 tests were good enough for the contest. But that's not the end of the story: we have 140 tests ;)↵
</spoiler>↵
↵
