Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

Notes 1: AtCoder ABC 133F [Easy]

Правка en30, от NeoYL, 2023-12-31 12:37:32

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 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 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

Code

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

Теги tree, segment tree, weighted graph, counting

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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> \n```cpp' -> '\n<spoiler summary="Code"> \n```cpp'
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)