TL;DR : I created a practice contest that contains 6 problems that use the same underlying DP idea.
https://mirror.codeforces.com/group/7Dn3ObOpau/contest/532384
I will publish the blog soon. Till then, feel free to discuss your approach in the comment section.
DP on distinct subsequences is one of the easiest DP to implement, but also the hardest DP to come up with. It is like an optical illusion, where at the start, you’d think that it’s impossible for such a simple code to work, but once you finally understand how the algorithm works, you’d think that the problem was a cakewalk.
To truly appreciate the beauty of the solution, it’s important that, before reading the blog, you spend a significant amount of time attempting all the 7 problems that I’ve created.
P.S : The problems are untested, if you see any issues, do let me know.
thank you!
Nice submissions. Would you like to share a short summary of your approach for each problem?
blogg