adaptatron's blog

[Tutorial + Contest] : Back to basics after 8 years ft. Edu166D Balanced Parenthesis on Segments
By adaptatron, 5 months ago, In English

The last Educational round contained an interesting problem D on Balanced parenthesis, which becomes almost trivial if someone has read this 8 year old comment by tenshi_kanade that talks about a much easier problem

Count the number of substrings that are balanced parenthesis.

I created a blog that talks about this idea in a bit more detail and also discusses how to modify the solution of this problem to make it work for the Edu problem. I also created practice problems on it so that you can submit your $$$O(n^2)$$$ and $$$O(n)$$$ approach. This is the contest link https://codeforces.net/group/7Dn3ObOpau/contest/527306

https://cfstep.com/training/tutorials/general-techniques/balanced-parenthesis-on-segments/

The problems are untested. If you see any issues, please let me know.

If you need any help or hints for the practice problem, you can ask on my Discord Server or on the Twitter thread. In case you are interested, you can also checkout my youtube channel

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

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

Nice solution ,but i was only able to follow upto O(n^2) due to segment tree.

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

    No worries. Understanding the $$$O(n^2)$$$ algorithm is in fact the most difficult part of the blog.

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

Nice blog. Rest of the website seems useful too.

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

Using Segment Tree requires a lot of minor optimizations or else it gives TLE. Took me 4 submissions before I got AC :'-)

Time to add sparse table to my template...

→ Reply
  • »
    »
    5 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Not really. Atcoder library already provides a max_right function that does binary search inside the segment tree making the time complexity $$$O(n \cdot log(n))$$$. Easier than learning Sparse Table.

    Update : I also added code samples of how to use the max_right function in this context.

    → Reply