Help with Ra-One Digit DP Python Solution

[master_coder09]

Can someone please help me optimise this solution gives TLE for Ra-One Digit DP problem. Thanks

[simes]

What solution? Did you mean to put a link or paste in some code?

[master_coder09]

Yes my bad : https://ideone.com/IGUbsU 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)

[simes]

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?

[master_coder09]

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.

[simes]

There aren’t any solvers in Python 3, or Pypy, and only one in Python 2.7. Perhaps it’s really hard to solve with Python? The time limit of 0.1 second is ridiculously short, even for a compiled language.