TheAiro's blog

By TheAiro, history, 12 months ago, In English

Hi, I am having difficutlties with this CSES problem "Book Shop". Firstly I implemented it recursively, but it gave me TLE. (Link). I've also been trying to get into iterative dp, so I tried it too and it worked! (Link)

However, I don't understand why recursive approach doesn't pass. Maybe I have implemented it poorly?

Also, it seems that there is an approach with $$$O(x)$$$ space complexity, but I have no clue how it works.

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It might be because recursive functions use up the call stack and that can get expensive enough to get a TLE.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, recently I've had a dilemma whether to use iterative approach, or a recursive one. Iterative seems to get an upper hand here. But there got to be a way for recursive approach to pass...

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The issue is CSES. They have very strict time limits.