Can someone please look my code for POLES on HackerRank.
Problem Link - Programming Problems and Competitions :: HackerRank
Solution Link -
Programming Problems and Competitions :: HackerRank
Please explain why it can not pass time limit & what approach should be used then
Thanks in advance
1 Like
Your solution is O(n^2k) whereas the intended solution is O(nk).
Have a look at convex hull optimizations for dynamic programming.
Helpful link: Dynamic Programming Optimizations - Codeforces
2 Likes
Your code is failing in these three lines. Please make sure that to make your program in a given constraint otherwise TLE will definitely be come.
for (i=0;i<n-1;i++)
for(j=1;j<min(k,i+2);j++)
calculate(n-i-1,j);
Minimise the looping or think another approach if you can!
Good Luck!
O(knlog(n)) solution is also sufficient to fit in TL . can be solved using divide and conquer dp optimization.
Can you please explain more on how to solve it using divide & conquer DP optimization @sacheendra9044