Editorial for Wesley's Anger Contest 6 Problem 5 - Canadian Christmas Cactus
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For , we can see that you can always add
edges. We will show how to do this later.
Subtask 1
For the first subtask, we can see that there are at most edges that can be added. Since
, at most
edges can be added. We can brute force all
subsets of edges added and ensure that each added edge (which forms a new cycle) does not intersect with any other cycles. Alternatively, we can see that there will only be at most
added edges and we can brute force all possible triples.
Time Complexity: or
where
Subtask 2
Consider the post traversal order of vertices after arbitrarily rooting the tree. For each vertex, we will repeatedly pick two of its unmatched children, add an edge between them, and mark them as matched. We can see that this will result in either or
unmatched children. If there is
unmatched child, then we will add an edge between that child vertex with the parent of the current vertex and mark both as matched. We can see that each edge is only a part of at most
cycle. We will then repeat this for each vertex in the post traversal order. At the end, the root vertex will always remain unmatched, along with at most
other vertex. Since each edge added results in
vertices being matched, we can see that this algorithm will always produce
edges.
Time Complexity:
Comments