Блог пользователя adaptatron

[Video] : Optimizing DP with Segment Trees ft. CF2019D: Speedbreaker
Автор adaptatron, 2 месяца назад, По-английски

I created a video editorial talking about how to use Atcoder Library's Segment Tree to optimize CF2019D: Speedbreaker

https://youtu.be/GyBA_nK4qiw?si=E5qw4X4FLHO5j--_

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very hard problems

→ Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I dont get it, D was extremely simple. You just have to track the first and last occursnce of each character, and then keep intersecting the segments.

    → Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

A 20 line implementation would reach $$$O(n)$$$ without segment trees on this problem.

→ Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, I agree Segment Tree might be an overkill for this problem. However, I arrived at the segtree solution without a lot of efforts, hence wanted to share an alternate solution from the editorial.

    Also, looking at submission count of Problem C (6529) vs Problem D (1373), a lot of people did not submit the overkill segtree solution, possibly because they were not aware of such data structures or thought process of reducing the problem to a standard domain, hence the video.

    → Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please explain your code and thought process of this problem ?

    → Ответить