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_a1_a2_...*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" [email protected] ha scritto:

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_
a1_a2_...*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
#1 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AD8chF-sQHfEubIqHPE0677OK7ESAkxaks5qp6HVgaJpZM4J7uh5
.