HackerRank Week of Code 30 - POLES Problem

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