Here is Problem

While accept recursive ,why this dp approach get tle

here is my Solution

pls help it out .I given more than 3 hr continuously .

thanks in advance

Here is Problem

While accept recursive ,why this dp approach get tle

here is my Solution

pls help it out .I given more than 3 hr continuously .

thanks in advance

Here is my TopDown aka Recursive + Memo Solution Link

And this one is bottom-up Link

Hope so u will understand my solution I will look at your solution if I will find anything wrong I will tell you.

thanks

I think that TLE was due to setting dp array default as 0 because your answer itself for anycase can be 0 so choosing -1 will be a good choice because checking (dp[i][j]==c) mainely tells us wheather we have calculated that value beforehand or not in case of 0 u can not tell wheather u have calulated that or not because answer for any case can be 0 in that case your dp array will be worthless so if cost for every agent is 0 in that case your previous stored results will be useless because cost will be always 0 and you are checking dp[i][j]>0 .Second thing taking min of mod and recurive call will ensure your value will never pile up other wise multiple calls will sum up multiple mod and may cause overflow.

I modified your code a little bit it’s working now Link.

1 Like

thanks alot ,i am just beginner in dp .

Appreciate your effort

Can u tell fault in this solution?

https://www.codechef.com/viewsolution/39169927

gives correct answer for sample test cases though

You are doing a mistake you are checking for -1 condition in the middle of optimization there is a chance that a person can not choose default at a point but can choose a cost agent but you are not even going to cost condition in this case u are just outputting -1 and returning from the function.

These are your modified working codes.

Link1

Link2