Can someone please help me optimise this solution gives TLE for Ra-One Digit DP problem. Thanks
created
Aug '23last reply
Jun '24- 6
replies
- 341
views
- 3
users
- 1
like
- 4
links
Yes my bad : https://ideone.com/IGUbsU1 This is the link of the Ideone. I am also pasting my code here :
from functools import cache
t = int(input())
for i in range(t):
lst = input().split(" ")
l = lst[0]
r = lst[1]
dic = {}
@cache
def f(i, flag, even, odd, nums):
if (i >= len(nums)):
if ((odd-even) == 1):
return 1
return 0
take = 0
if (i % 2 != 0):
if(flag==True):
for j in range(10):
take += f(i+1, True, even, odd+j, nums)
else:
for j in range(int(nums[i])):
take+=f(i+1, True, even, odd+j, nums)
take+=f(i+1, flag, even, odd+int(nums[i]), nums)
else:
if(flag==True):
for j in range(10):
take += f(i+1, True, even+j, odd, nums)
else:
for j in range(int(nums[i])):
take+=f(i+1, True, even+j, odd, nums)
take+=f(i+1, flag, even+int(nums[i]), odd, nums)
return take
val1 = f(0, False, 0, 0, str(int(l)-1))
val2 = f(0,False, 0, 0, r)
val2 -= val1
print(val2)
Memoise! If f has already calculated the answer for a given set of arguments, return that answer. Otherwise, calculate it, then save and return it.
Is this what you intended the unused dic to be used for?
edit: ah I see that’s what the @cache decorator does.
edit 2: could this cache get very large when it’s used for multiple test cases? All that memory management has got to take some time. Would a home grown DP cache be more efficient, since its lifetime would be for a single test case. Or am I showing my ignorance of Python’s cleverness?
Yes I tried using the dictionary for memoizing seeing that It was taking more space I memoised using the @cache decorator But it still gives me a TLE.
There aren’t any solvers in Python 3, or Pypy, and only one in Python 2.71. Perhaps it’s really hard to solve with Python? The time limit of 0.1 second is ridiculously short, even for a compiled language.
9 months later
Hello @master_coder09 
off course as per my knowledge you can consider some following tips:
-
Insure you are using an effective dynamic programming approach. This generally involves defining your countries and transitions precisely to avoid spare calculations.
-
Also you can check if you are using further memory than necessary. occasionally, reducing the memory footmark can ameliorate performance significantly.
-
You can review the complexity of your solution. However, suppose about ways to reduce it, similar as optimizing circles and data structure
Please share your current code or specific parts of it, we might be able to provide more targeted advice.