_trie_again's blog

Help me to debug the python code
By _trie_again, history, 19 months ago, In English

Hi everyone, i have started learning python . So i want to know what is the bug in my program: The same code 204659837 in c++ works fine, but in python its not even working on sample tests. Please enlighten me. My python code:

INF=2e18

def dfs(idx,cnt)->int:
	if(idx>=n):
		if(cnt!=3):
			return -INF
		return 0
	ans=dp[idx][cnt]
	if(vis[idx][cnt]):
		return ans
	vis[idx][cnt]=1
	ans=0
	ans=max(ans,dfs(idx+1,cnt))
	if(cnt<3):
		if(cnt==0):
			ans=max(ans,dfs(idx+1,cnt+1)+(a[idx]+idx+1));
		elif(cnt==1):
			ans=max(ans,dfs(idx+1,cnt+1)+a[idx]);
		elif(cnt==2):
			ans=max(ans,dfs(idx+1,cnt+1)+a[idx]-(idx+1));
	dp[idx][cnt]=ans
	return ans

for i in range(int(input())):
	n=int(input())
	a=list(map(int,input().split()))
	dp=[[-1]*5 for i in range(n+5)]
	vis=[[0]*5 for i in range(n+5)]
	print(dfs(0,0))
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The bug you're looking for is on line 13 of your python solution:

ans=max(ans,dfs(idx+1,cnt))

should be (based on your c++ solution)

ans=dfs(idx+1,cnt)

This makes your code pass the samples but it gives RTE on test 5. I don't know what is causing this.

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

    The runtime error is probably occurring because, by default, Python has a recursion depth limit of only 1000. You can increase this limit by calling sys.setrecursionlimit( new limit ), but then you may run into the problem of limited system stack size. According to the comments on this blog post, you can use the threading module to increase the system stack size, although I haven't tried this.

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

      According to this , i also did same by using sys.setrecursionlimit() and threading.stack_size() and it passed in python 3 and giving me MLE in PyPy 3-64. Now i am more confused lol.

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

        welcome to the painful world of Python coding.

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

          Well, i think python has its own advantage of writing less lines of code. Thats why i started liking it. But still c++ >> any language in cp.

          → Reply