In relation to Counting the ways

[peppeweb]

Hi , I''m working on the mentioned challenge, and I see you made a CPP version. With an algorithm of dynamic programming i reach good results, when L and R become LONG type, then it take forever to calculate even only one.

So i wonder if you had the same issue and how you tackled it/

Giuseppe

[jvujcic]

Hi,

Yes, DP will only get you about 30% points. Complexity of the basic DP algorithm is O(N_R) which in the worst case is 10^18. I didn't solve it but this was the hardest problem on the week of code competition. I think the idea was to use DP for smaller cases, that is for all F(m) where m<N_a1a2...*aN. For bigger m you had to use Lagrange interpolation somehow. If you want I can check the solution and write it here.

[peppeweb]

Hi Josip,

From the mathematical perspective I also was thinking about some sort of integration between the two points but I thought was too far and the category of the exercise is DP.

I didn't try the Lagrange interpolation to define the F(x), thank for the hint, will have a look and let you know the results.

G

Il 14 set 2016 09:27, "Josip Vujcic" notifications@github.com ha scritto:

Hi,

Yes, DP will only get you about 30% points. Complexity of the basic DP algorithm is O(NR) which in the worst case is 10^18. I didn't solve it but this was the hardest problem on the week of code competition. I think the idea was to use DP for smaller cases, that is for all F(m) where m<N a1a2...*aN. For bigger m you had to use Lagrange interpolation somehow. If you want I can check the solution and write it here.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/jvujcic/HackerRank/issues/1#issuecomment-246928862, or mute the thread https://github.com/notifications/unsubscribe-auth/AD8chF-sQHfEubIqHPE0677OK7ESAkxaks5qp6HVgaJpZM4J7uh5 .