Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

dev_ankitp's blog

By dev_ankitp, history, 6 weeks ago, In English,

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

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

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

good job!

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice work, if possible make it more detailed, attach references of codeforces blogs, cp-algorithms blogs wherever possible.

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

link to All CSES Problems please

»
5 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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
»
5 weeks ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

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

      Such a clean and easy solution! Thank you:)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +2 Vote: I do not like it

      Yea i got it this time! and that delaying adding elements to window idea is pretty cool thank you:)

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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