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

Правка en14, от lior5654, 2021-05-08 01:45:27

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

Solution By FiveSixFiveFour

This was very challenging to implement during the contest yet eventually I got AC 10 minutes before the end of the round. Thanks for the contest! :D

Теги 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)