[Community Editorial] Codeforces Round #720 (Div.2) Problem D — Nastia Plays with a Tree

Правка en4, от lior5654, 2021-05-08 00:27:47

Hello Codeforces!

Today was Codeforces Round #720 (Div.2), in which I solved problem D — Nastia Plays with a Tree. As I find my solution different from the solutions I heard of after the contest, I will explain it in detail in this blog post. I will note that you still might find value in reading this if you solved the problem, as my proposed solution also maintains at every stage the graph being a forest (i.e I don't create any cycles).

The Solution

Note that in this editorial, when I write simple path, I mean a simple path between two nodes without having extra edges going from any of the nodes that do not belong to that simple path, or simply a node not connected to anything (this will be clearer once we see drawings).

We should first note that bamboo is simply a tree that looks like a single line of connections (i.e a simple path).

We observe that given the sequence of moves the order we delete/link edges in does not change the resultant underlying graph. We consider the following question: how can we delete edges such that we can link the remaining forest via link operations to make a bamboo after we delete all of them?

Well, we want to achieve a simple path in the end, and a simple path can only be broken into nonintersecting simple paths, therefore after edge deletions, we should have a set of nonintersecting simple paths.

Now, our motivation is to take some pen & paper and draw how such a set looks like (not necessarily the optimal one) (in this editorial I cheat with CSAcademy Graph Editor). **Note that for convenience and as in many tree problems, we root the tree at an arbitrary node.

Suppose we are given the following tree (rooted at node 1):

We can convert it to a set of non-intersecting simple paths in multiple ways, one of which is deleting 4->10, 5->13 & 5->7, and if we were to apply this way we would end up with the following set of simple paths:

If we look at subtrees of the original tree and what they turned into after the deletion, we observe that if a node has outgoing edges to 2 of its original children from the original subtree then that node must not be connected to its parent.

This leads to an approach of dynamic programming over subtrees & an observation is that we can utilize the following state: whether or not our subtree root is connected to its parent. The motivation for this state is exactly what we state above, in order to connect to more than 1 child we must not be connected to our parent.

Let $$$sdp[c]$$$ be the minimum cost to convert $$$c$$$'s subtree into a set of disjoint simple paths, given that we delete the edge from $$$c$$$ to its parent, and let $$$cdp[c]$$$ denote the cost given that we do not delete the edge from node $$$c$$$ to its parent. So in $$$sdp$$$ we allow connecting to 2 children and in $$$cdp$$$ we do not allow that, but for $$$sdp$$$ we add a cost of 1 (deleting the edge to the parent). Note that in this way, the root $$$sdp$$$ 's value will contain 1 more than the actual answer (because the root doesn't have a parent so we add 1 for no reason) but as you'll see we don't use that numerical value in our construction.

For the construction, when we calculate the $$$dp$$$ values we also want to store what edges we do keep.

Теги div2, 720, trees, dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en14 Английский lior5654 2021-05-08 01:45:27 6 Tiny change: ' and $d_1 <= 0$, then ' -> ' and $d_1 \le 0$, then '
en13 Английский lior5654 2021-05-08 01:39:37 66
en12 Английский lior5654 2021-05-08 01:35:40 1 Tiny change: 'O(n\log(n)$, depend' -> 'O(n\log(n))$, depend'
en11 Английский lior5654 2021-05-08 01:32:18 2386 (published)
en10 Английский lior5654 2021-05-08 01:12:51 184 Tiny change: 'f $d_0 \gr 0$, \n\n' -> 'f $d_0 \grt 0$, \n\n'
en9 Английский lior5654 2021-05-08 01:00:18 349 Tiny change: 'ly in $O(nlog(n))$ v' -> 'ly in $O(n*log(n))$ v'
en8 Английский lior5654 2021-05-08 00:54:59 49
en7 Английский lior5654 2021-05-08 00:53:35 14
en6 Английский lior5654 2021-05-08 00:52:54 1567
en5 Английский lior5654 2021-05-08 00:35:47 937
en4 Английский lior5654 2021-05-08 00:27:47 790
en3 Английский lior5654 2021-05-08 00:19:58 620 Tiny change: 'tQc.png)\n\n\n' -> 'tQc.png)\ntest\n\n'
en2 Английский lior5654 2021-05-08 00:07:09 1224
en1 Английский lior5654 2021-05-07 23:40:15 995 Initial revision (saved to drafts)