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

Автор _trie_again, история, 18 месяцев назад, По-английски

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

»
18 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    18 месяцев назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

    • »
      »
      »
      18 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        18 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        welcome to the painful world of Python coding.

        • »
          »
          »
          »
          »
          18 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.