Notes 1: AtCoder ABC 133F

Revision en26, by NeoYL, 2023-12-14 19:26:18

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

This is the first episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), which are completely solved by myself without looking at the editorial, that are both interesting and educational.

If you want to motivate me to write a continuation (aka note 2), 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.

Problem link: ABC133F

Try to solve the task independently before continuing the blog.

Hint
Incomplete solution

That reduces the problem to $$$O(N ^ 2)$$$, lets optimize it!

optimization used

This allows an $$$O(N log N)$$$ solution

AC code link

Spoiler

Feel free to ask anything about the task. I will try to respond them if I am free.

Tags tree, segment tree, weighted graph, counting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en30 English NeoYL 2023-12-31 12:37:32 7
en29 English NeoYL 2023-12-14 19:34:13 18
en28 English NeoYL 2023-12-14 19:32:15 348
en27 English NeoYL 2023-12-14 19:26:45 17 Tiny change: '\n<spoiler> \n```cpp' -> '\n<spoiler summary="Code"> \n```cpp'
en26 English NeoYL 2023-12-14 19:26:18 5298
en25 English NeoYL 2023-12-14 17:59:14 5 Tiny change: 'timization">\nWe can' -> 'timization used">\nWe can'
en24 English NeoYL 2023-12-14 13:29:32 12 Tiny change: ' summary="Half solution"' -> ' summary="Incomplete solution"'
en23 English NeoYL 2023-12-14 08:58:57 215
en22 English NeoYL 2023-12-14 08:57:58 141 Tiny change: ' summary="$O(N^2)$ s' -> ' summary=" $O(N^2)$ s'
en21 English NeoYL 2023-12-13 13:27:55 15
en20 English NeoYL 2023-12-12 13:33:13 4
en19 English NeoYL 2023-12-12 09:13:23 2 Tiny change: 'ed to add +1 to each n' -> 'ed to add $+1$ to each n'
en18 English NeoYL 2023-12-12 05:48:22 2 Tiny change: 'round 2400 ish proble' -> 'round 2400-ish proble'
en17 English NeoYL 2023-12-12 04:44:37 8
en16 English NeoYL 2023-12-12 03:55:24 86
en15 English NeoYL 2023-12-12 03:47:05 36 Tiny change: 'n problems, which ar' -> 'n problems (normally around 2300 ish problems), which ar'
en14 English NeoYL 2023-12-12 03:46:04 16
en13 English NeoYL 2023-12-12 03:45:29 20 Tiny change: 'note 2), an upvote would be ' -> 'note 2), a significant upvote from you would be '
en12 English NeoYL 2023-12-12 03:42:52 160
en11 English NeoYL 2023-12-12 03:38:43 22
en10 English NeoYL 2023-12-12 03:37:41 324
en9 English NeoYL 2023-12-11 19:35:45 4 Tiny change: 'at a point $p$. What do ' -> 'at a point. What do '
en8 English NeoYL 2023-12-11 19:34:44 19 Tiny change: 'e able to continue from here' -> 'e able to solve the problem from here'
en7 English NeoYL 2023-12-11 19:27:44 64
en6 English NeoYL 2023-12-11 19:26:56 40 Tiny change: 'e set.\n\n[AC co' -> 'e set.\n\nThis allows an $O(N log N)$ solution\n\n[AC co'
en5 English NeoYL 2023-12-11 19:26:07 20 Tiny change: 'n the path.\n\nNow' -> 'n the path * new weight length.\n\nNow'
en4 English NeoYL 2023-12-11 19:25:11 262
en3 English NeoYL 2023-12-11 19:23:21 8421 (published)
en2 English NeoYL 2023-12-11 19:07:37 7364
en1 English NeoYL 2023-12-11 19:00:00 1500 Initial revision (saved to drafts)