# Project Euler #114: Counting block combinations I

# Project Euler #114: Counting block combinations I

+ 1 comment Did not expect the major obstacle to be

`OverflowError`

from exponentiation of`(sqrt(5)+1)/2`

. Horrible use of diagonalization without numpy.**EDIT**: Learned the`Decimal`

module, which helps in calculating very large decimal value. But got stuck with insufficient`decimal.getcontext().prec`

as the value after exponentiation is very, very large (thousands? millions? or even more of digits), while I want every single digit to the left of the decimal point. I wonder if anything could be done to this intermediate step, as there is still crucial ahead before performing the final modulo opeartion. And the I obtained is also subject to significant error as it is found with`np.linalg.eig()`

. Heck, there is even`decimal.Overflow: above Emax`

!**EDIT 2**: When I looked closely, unfortunately, this approach seems to start deviating from the results of the DP approach (which is slower but correct) for (`763701899`

vs`763701898`

). Using`numpy`

without`Decimal`

is even worse. When the input is`2000 3`

then it is the embarrassing`973324784`

vs`nan`

vs`709134169`

.**EDIT 3**: Stupid me to have thought about diagonalization. It's not the only option to achieve matrix exponentiation. Simple recursive divide and conquer like mergesort can do the job. And one more thing, construct your matrix according to .Now perhaps I'm ready for Problem 109 Darts.

+ 1 comment I am getting wrong answer for test case 11. Others are correct. There is no overflow problem, as I also checked using BigInteger, same result. Can somebody pointing ouut my mistake?

+ 1 comment Hi, I have tried this problem a few times and keep failing due to timeout (a bit frustrating). Here's my code which runs O(n). It is based on the idea that f(n) = 2* f(n-1) - f(n-2) + f(n-m-1). Can someone give any hint what would be a better solution?

def f(n, m): if n < m: return 1 if n == m: return 2 a = [1] * (m + 1) a[m] = 2 value, p = 0, 0 for _ in range(m + 1, n + 1): value = 2 * a[(p+m) % (m+1)] - a[(p+m-1) % (m+1)] + a[p] a[p] = value p = (p+1) % (m+1) return value

No more comments

Sort 3 Discussions, By:

Please Login in order to post a comment