Getting Tle In the submission

#1

Hello…
Good Morning…
I am solving this question from Hackerearth…

I have solved this question using DP+MEMOIZATION…
even now it is showing Tle…

So i thought that do the precomputation for each value of n from 2 to 10**4… Now after that it was showing TLE in all test cases…

These are the two submission…
1)https://www.hackerearth.com/submission/51561426/
2)https://www.hackerearth.com/submission/51561457/

Please see this.
Thanks

#2

I saw your code, it uses 2-D dp, but actually this is 1-D dp on N which makes it faster.
See this for implementation https://ide.codingblocks.com/s/393164, if you have any doubts in this please ask, even though the code is straight forward.

#3

Hii…
I am not able to understand… What have you done int the if statement after the second loop… Can you explain it…
Thanks

#4

Actually i got what are you doing there…
Just wanted to get confirmed… That what i understood is right or not…
Thanks

#5

Could you please write the line number or copy the code snippet here? I am not getting which part :sweat_smile:

#6

This part…
if(v[j]<=i&&((dp[i-v[j]]!=0)||(i-v[j]==0)))

#7

Okay this is simply checking if we can make i using v[j] or not.
For this v[j] must be less than i in consideration.
Second condition is that dp[i-v[j]] is not zero, something we do even in that steps problem

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.