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

Revision en1, by lior5654, 2021-05-07 23:40:15

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

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?

Tags div2, 720, trees, dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en14 English lior5654 2021-05-08 01:45:27 6 Tiny change: ' and $d_1 <= 0$, then ' -> ' and $d_1 \le 0$, then '
en13 English lior5654 2021-05-08 01:39:37 66
en12 English lior5654 2021-05-08 01:35:40 1 Tiny change: 'O(n\log(n)$, depend' -> 'O(n\log(n))$, depend'
en11 English lior5654 2021-05-08 01:32:18 2386 (published)
en10 English 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 English lior5654 2021-05-08 01:00:18 349 Tiny change: 'ly in $O(nlog(n))$ v' -> 'ly in $O(n*log(n))$ v'
en8 English lior5654 2021-05-08 00:54:59 49
en7 English lior5654 2021-05-08 00:53:35 14
en6 English lior5654 2021-05-08 00:52:54 1567
en5 English lior5654 2021-05-08 00:35:47 937
en4 English lior5654 2021-05-08 00:27:47 790
en3 English lior5654 2021-05-08 00:19:58 620 Tiny change: 'tQc.png)\n\n\n' -> 'tQc.png)\ntest\n\n'
en2 English lior5654 2021-05-08 00:07:09 1224
en1 English lior5654 2021-05-07 23:40:15 995 Initial revision (saved to drafts)