15411019's blog

Runtime error issue
By 15411019, history, 6 years ago, In English

Hey Guys,

I am trying to solve this problem [contest:260][problem:A](https://codeforces.net/contest/455/problem/A) tagged DP. I am getting runtime error for my submission in case of larger inputs. 

n =int(input())
arr = [int(x) for x in input().split()]

freq = [0]*(n + 1)

for i in arr:
    freq[i] = freq[i] + 1

dic = {}
def dp(a):
    if a in dic:
        return dic[a]
    if(a==0):
        return 0
    if(a==1):
        return freq[1]
    res = max(dp(a-1), dp(a-2)+a*freq[a])
    dic[a] = res
    return res

print(dp(n))

Can anyone please explain what I am doing wrong, I am a beginner. Any help will be appreciated.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by 15411019 (previous revision, new revision, compare).

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

I think this issue is provided by max recursion size in python try solve it in one loop

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You have two errors, first is that the ak can be up to 105 but you are using effectively using n as an upper bound. You can solve this by just switching all the n with 105.

Your second problem is that python really can't handle recursion. By default the recursionlimit is set 1000, meaning you can't do deeper recursion than 1000 without getting an exception. It is possible to change this number by using sys.setrecursionlimit but because recursion is so bad in python it will still just crash if you go too deep, maybe 10000 could work but any higher than that and it will probably crash (from my own experience). So never do deep recursion in python.

This is one of my biggest gripes with python. However there are a couple of ways to get around it. One is to manually do recursion using your own stack. I usually do this for most dfs problems. But for this problem you can just do everything with a for loop instead of recursion.

With those two problems fixed the solution passes without any problems.

EDIT: Also note that I submitted with pypy3 instead of python3, pypy3 is just another interpreter for python3 which usually runs a lot quicker than cpython3 (the interpreter used if you submit with python3).

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

    Thank you for the help. Does other languages(for example-C++) also suffers from the same problem? I found most of DP problems are easier to solve using recursion compared to the bottoms up approach. Maybe I should shift to some other language.

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

      I think this is pretty much just a python thing, sure there are recursion depth limits in other languages as well but 1000 is extremely low.

      And yeah if you want to solve DP problems with recursion then switch language to pretty much anything but python. Every language has it strengths and weaknesses, and recursion is probably one of it biggest weaknesses of python (apart from its speed, and the speed is even worse than usual because codeforces uses 32 bit python which is super slow with integers that doesn't fit inside a 32 bit int). But not everything is bad with python, I still like to use it for many problems, but not when I need recursion or speed.

      → Reply