dev_ankitp's blog

All CSES Problems Editorial [ONGOING]
By dev_ankitp, history, 5 years 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

Comments Comments (14)
| Write comment?
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

good job!

→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

link to All CSES Problems please

→ Reply
»
5 years 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
→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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

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

      Such a clean and easy solution! Thank you:)

      → Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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:)

      → Reply
      • »
        »
        »
        »
        5 years 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

        → Reply