Блог пользователя dev_ankitp

Автор dev_ankitp, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

good job!

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

link to All CSES Problems please

»
4 года назад, # |
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
»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +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