Why get tle for this code

1

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

2

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.

3

thanks

4

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
5

thanks alot ,i am just beginner in dp .
Appreciate your effort :slight_smile: :blush:

6

Can u tell fault in this solution?
https://www.codechef.com/viewsolution/39169927
gives correct answer for sample test cases though

7

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