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.com/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
Nice solution ,but i was only able to follow upto O(n^2) due to segment tree.
No worries. Understanding the $$$O(n^2)$$$ algorithm is in fact the most difficult part of the blog.
Nice blog. Rest of the website seems useful too.
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...
Not really. Atcoder library already provides a
max_rightfunction 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_rightfunction in this context.Thank you for this info!