Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

anmolsainiii23's blog

Why not Recursive?
By anmolsainiii23, history, 7 months ago, In English

Hi I was wondering why can't we use recursive Solution for Coin Piles Solution. This is the Problem

I have tried recursive solution but end up getting TLE and Runtime Error. Can anyone explain whether we can use Recursion or Dynamic Programing. This is my Solution.

This is my Soluion

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

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

See the constraint on a, b (1e9). It seems yours code taking O(ab) time and memory

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

    Yeahh. Ok got it. But the recurrence was correct?

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

      apart from (time / space complexity) yours recurrence solution was correct, but generally recursive solution was slower than dp.

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

        Yeah that I agree. I just tried solving CSES and CSES is actually hard to solve. Considering the constraints doesn't favour Bruteforce Solution. They actually prefer Optimized one.

        → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You also can solve it as O(1)

      → Reply