Notes 3: Codeforces 1795F Div 2

Revision en1, by NeoYL, 2023-12-19 13:12:28

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the third episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), which are completely solved without looking at the editorial, that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog. The problem on these notes should give a very interesting solution and will likely be optimizations problems (I feel like these problems have an IOI-style, which requires you to find some incomplete solution first then find the final solution using it).

If you want to motivate me to write a continuation (aka note 4), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Paraphrase problem:

Given a tree with $$$N$$$ nodes. Given $$$K$$$ nodes, $$$a_{1},a_{2},a_{3},...,a_{K}$$$. Initially these nodes are covered black and the remaining are colored white. Operation $$$X$$$ means that we will move $$$a_{(X-1) mod K + 1}$$$ and spread the black color to a neighbouring node of your choice. This means we will move $$$a_{1},a_{2},a_{3},...a_{K},a_{1},a_{2}...$$$. No blocks can be colored black twice.

Prerequisites
Hints
Solution
Code
Tags binary search, dp, brute force, implementation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en17 English NeoYL 2024-01-01 19:49:55 8
en16 English NeoYL 2023-12-31 12:36:26 9
en15 English NeoYL 2023-12-31 12:36:07 66
en14 English NeoYL 2023-12-27 06:26:34 41 Tiny change: 'oiler>\n\n\n<spoil' -> 'oiler>\n\nCan you continue the problem from here?\n\n<spoil'
en13 English NeoYL 2023-12-26 20:24:13 52 Tiny change: 'ntation. Xd\n' -> 'ntation. XD\n\nHope you guys learnt something from this blog.\n'
en12 English NeoYL 2023-12-26 20:14:37 2 Tiny change: 'ace std;\n\nusing i6' -> 'ace std;\nusing i6'
en11 English NeoYL 2023-12-26 15:23:21 1 Tiny change: 'Paraphrase problem:\' -> 'Paraphrased problem:\'
en10 English NeoYL 2023-12-26 15:22:49 253
en9 English NeoYL 2023-12-24 11:11:49 1 Tiny change: ' $x$ moves It must s' -> ' $x$ moves? It must s'
en8 English NeoYL 2023-12-24 11:11:08 23
en7 English NeoYL 2023-12-24 11:10:27 11
en6 English NeoYL 2023-12-22 11:04:58 206
en5 English NeoYL 2023-12-22 10:02:52 3 Tiny change: 'mentation.\n' -> 'mentation. Xd\n'
en4 English NeoYL 2023-12-22 05:13:22 78
en3 English NeoYL 2023-12-21 04:38:31 7 Tiny change: 'move down or up. \n</s' -> 'move down and up. \n</s'
en2 English NeoYL 2023-12-19 13:15:16 98 (published)
en1 English NeoYL 2023-12-19 13:12:28 4005 Initial revision (saved to drafts)