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.

[bamo_1234]

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

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.