I've recently started doing CSES problems I found them quite interesting. So far I've completed around first 100 problems (Completed till GraphAlgorithms) I've seen a lot of people asking for help, here are all of my submissions and explanations.
https://github.com/ankitpriyarup/CSES_ProblemSet_Solution
PS: To make it look clean I haven't included my ugly header, in case you want to see it click here
Problemset: https://cses.fi/problemset/list/
Refer this book side by side for theoretical knowledge: https://cses.fi/book/book.pdf
good job!
Nice work, if possible make it more detailed, attach references of codeforces blogs, cp-algorithms blogs wherever possible.
Thanks! I'll add reference links soon.
link to All CSES Problems please
I'll keep updating the repository as I'll do more problems. For additional range query editorial you can refer: https://mirror.codeforces.com/blog/entry/77128
here!
Thanks and a request to everyone to post all the doubts in this blog only instead of creating different posts.
Hey ! i am not entirely getting how your solution for this problem works. It would be quite helpful if you could elaborate a bit more...plzz.
The way you can do that problem is sliding a multiset so we first fix either the left point or right point(doesn't matter). So if we fix the left point of the window at i, then we have a multiset that contains the prefix sums of [i+a-1, ...., i+b-1]. Since multisets let us retrieve the largest/smallest element in log n time, this solution works in NlogN. We also need to maintain prefix sums. This solution fixes the right point: https://pastebin.com/WuS6H09J This solution fixes the left point: https://pastebin.com/af9LfUY7
Such a clean and easy solution! Thank you:)
If we maintain a prefix sum array of the original array our problem breaks down to finding L & R points (where L <= R) such that prefSm[R]-prefSum[L-1] is maximum possible and R-L+1 (all elements within) is between a to b. We can iterate over all points (i = 1 to N) and fix R=i after that we just need to find a point L which is at least a distance away but not more than b distance.
We can do this easily in quadratic time but to do so in linear time we will need to use the idea of sliding window maximum problem. We can delay pushing elements to our sliding window by a (keeping the intended gap of a) and maintain a size keeping only b-a+1 elements in the window hence fulfilling our second constraint.
Now look at my solution, hopefully you will be able to understand it now: https://github.com/ankitpriyarup/CSES_ProblemSet_Solution/blob/master/2%20Sorting_and_Searching.md#maximum-subarray-sum-ii
Yea i got it this time! and that delaying adding elements to window idea is pretty cool thank you:)
If you want to be even more overkill, u can preprocess with a sparse table so you don't have to slide a multiset and just use RMQ in O(1) which would be O(Nlog) for preprocessing and then O(N) to find answer
Nice!