We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

The infinite number of darts are not very friendly. I suppose dynamic programming is not applicable for larger input. My DP approach got TLE #7, #8 and MemoryError from #9 onwards. If you're interested, here is part of my code snippet:

EDIT: Learn about linear recurrence relation matrix (of size ), and then think about constructing the matrix (of size ) that can be feeded to a cumulative vector. Start with the vector [1] + [0] * 60. Perform matrix exponentiation (divide and conquer, very straightforward) that is . And finally, pick the double ending elements from the final vector of . Problem 114 has a relevant approach.

## Project Euler #109: Darts

You are viewing a single comment's thread. Return to all comments →

The infinite number of darts are not very friendly. I suppose dynamic programming is not applicable for larger input. My DP approach got TLE #7, #8 and

`MemoryError`

from #9 onwards. If you're interested, here is part of my code snippet:EDIT: Learn about linear recurrence relation matrix (of size ), and then think about constructing the matrix (of size ) that can be feeded to a cumulative vector. Start with the vector`[1] + [0] * 60`

. Perform matrix exponentiation (divide and conquer, very straightforward) that is . And finally, pick the double ending elements from the final vector of . Problem 114 has a relevant approach.