adaptatron's blog

[Video] : Optimizing DP with Segment Trees ft. CF2019D: Speedbreaker
By adaptatron, 4 months 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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very hard problems

→ Reply
  • »
    »
    4 months ago, # ^ |
      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
»
4 months ago, # |
  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
  • »
    »
    4 months ago, # ^ |
      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
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes it's always useful to learn different ways to solve a problem.

      → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply