COINS-TLE why

What is wrong with my approach?

problem

Solution

p.s. The time limit is 9 sec. But I am getting TLE before 6 seconds. Shouldn’t the cod atleast run for 9 seconds before giving any verdicts?

Hi! I tried submitting your solution and found that the problem is because you’re pre- processing so many values which is not required for the problem. You can make changes to your solve() function only to get you the result.

You can also see my solution.

1 Like

If u are forming an iterative dp solution…and the problem requires the solution for values as large as 10^9… the solution will tle cause it will fill all the states which are not even required to be filled…causing unnecessary computation…so switch to recursive dp solution…which is also called lazy dp solution…as it will only memoize the states which are necessary…thus saving extra computation… :smiley:

1 Like

check my solution …its simple!
https://www.codechef.com/viewsolution/6990677

1 Like

Thank you guys. Learnt a new thing :slight_smile: