adaptatron's blog

[Video] : Optimizing DP with Segment Trees ft. CF2019D: Speedbreaker
By adaptatron, 2 years ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Very hard problems

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply