### dev_ankitp's blog

By dev_ankitp, history, 13 months ago,

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

• +44

 » 13 months ago, # |   +6 good job!
 » 13 months ago, # |   +1 Nice work, if possible make it more detailed, attach references of codeforces blogs, cp-algorithms blogs wherever possible.
•  » » 13 months ago, # ^ |   0 Thanks! I'll add reference links soon.
 » 13 months ago, # |   0 link to All CSES Problems please
•  » » 13 months ago, # ^ |   0 I'll keep updating the repository as I'll do more problems. For additional range query editorial you can refer: https://codeforces.com/blog/entry/77128
•  » » 13 months ago, # ^ |   +3
 » 13 months ago, # | ← Rev. 2 →   +1 Thanks and a request to everyone to post all the doubts in this blog only instead of creating different posts. By this one can search doubts in this single post only instead of googling it. This will also not pollute the blog feed
 » 13 months ago, # | ← Rev. 3 →   +6 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.
•  » » 13 months ago, # ^ |   +3 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
•  » » » 13 months ago, # ^ |   0 Such a clean and easy solution! Thank you:)
•  » » 13 months ago, # ^ |   +3 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
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +2 Yea i got it this time! and that delaying adding elements to window idea is pretty cool thank you:)
•  » » » » 13 months ago, # ^ |   +3 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
•  » » » » » 13 months ago, # ^ |   0 Nice!
 » 12 months ago, # | ← Rev. 2 →   0 Can you please explain how the Array Division problem is converted into a binary search problem? How is the answer found using Binary Search ?!!Problem is this (Array Division) --> Array Division Solution is this --> Ankit's SolutionAny help is much appreciated. This is going above my head.