Notes 1: AtCoder ABC 133F

Revision en25, by NeoYL, 2023-12-14 17:59:14

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.

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 here

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

#### History

Revisions

Rev. Lang. By When Δ Comment
en30 NeoYL 2023-12-31 12:37:32 7
en29 NeoYL 2023-12-14 19:34:13 18
en28 NeoYL 2023-12-14 19:32:15 348
en27 NeoYL 2023-12-14 19:26:45 17 Tiny change: '\n<spoiler> \ncpp' -> '\n<spoiler summary="Code"> \ncpp'
en26 NeoYL 2023-12-14 19:26:18 5298
en25 NeoYL 2023-12-14 17:59:14 5 Tiny change: 'timization">\nWe can' -> 'timization used">\nWe can'
en24 NeoYL 2023-12-14 13:29:32 12 Tiny change: ' summary="Half solution"' -> ' summary="Incomplete solution"'
en23 NeoYL 2023-12-14 08:58:57 215
en22 NeoYL 2023-12-14 08:57:58 141 Tiny change: ' summary="$O(N^2)$ s' -> ' summary=" $O(N^2)$ s'
en21 NeoYL 2023-12-13 13:27:55 15
en20 NeoYL 2023-12-12 13:33:13 4
en19 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 NeoYL 2023-12-12 05:48:22 2 Tiny change: 'round 2400 ish proble' -> 'round 2400-ish proble'
en17 NeoYL 2023-12-12 04:44:37 8
en16 NeoYL 2023-12-12 03:55:24 86
en15 NeoYL 2023-12-12 03:47:05 36 Tiny change: 'n problems, which ar' -> 'n problems (normally around 2300 ish problems), which ar'
en14 NeoYL 2023-12-12 03:46:04 16
en13 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 NeoYL 2023-12-12 03:42:52 160
en11 NeoYL 2023-12-12 03:38:43 22
en10 NeoYL 2023-12-12 03:37:41 324
en9 NeoYL 2023-12-11 19:35:45 4 Tiny change: 'at a point $p$. What do ' -> 'at a point. What do '
en8 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 NeoYL 2023-12-11 19:27:44 64
en6 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 NeoYL 2023-12-11 19:26:07 20 Tiny change: 'n the path.\n\nNow' -> 'n the path * new weight length.\n\nNow'
en4 NeoYL 2023-12-11 19:25:11 262
en3 NeoYL 2023-12-11 19:23:21 8421 (published)
en2 NeoYL 2023-12-11 19:07:37 7364
en1 NeoYL 2023-12-11 19:00:00 1500 Initial revision (saved to drafts)