Can someone please look my code for POLES on HackerRank.

Problem Link - https://www.hackerrank.com/contests/w30/challenges/poles

Solution Link -

https://www.hackerrank.com/contests/w30/challenges/poles/submissions/code/1300974988

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: http://codeforces.com/blog/entry/8219

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