# Project Euler #101: Optimum polynomial

# Project Euler #101: Optimum polynomial

+ 1 comment The way the test cases are provided for this problem is really weird.

I made a mistake but my code could only go wrong with one specific input value. However I could pass no test cases other than #0.

It misled me into thinking that my algorithm was wrong.

When I modified my code to handle this special case, I jumped from 0% to 100%. So this special value is included in all test cases aside from the sample.

Obviously, better distribution is possible.

+ 0 comments Just in case it mights help someone : 1.all these are binomial coefficients. 2.for the god of pythons, dont do (-1)**3000 (-_-)

+ 0 comments I cannot pass the test 8. Can anyone give some hints?

+ 1 comment I did the first test case correctly, but I timed out on all the other cases. I am using modular Gaussian elimination to find the optimum polynomials. Is there a recurrence realtionship that I should be using instead of the costly O(n^3) operation.

+ 0 comments It's getting very messy to deal with system of linear equations and polynomials without using numpy and sympy.

**EDIT**: It comes to me as a bit of surprise, that even with the beautiful use of binomial coefficients, the result is all TLE except the first test case. And when I look closely, it seems that it takes more than 6 seconds to calculate the original sequence terms with the polynomial coefficients provided.Interestingly, when I suspect that the input

`A`

are too large to be multiplied and add the modulo to it before calculation, now it takes more than 7 seconds to get those terms. It couldn't be the problem with`map(int, raw_input().split())`

, could it?**EDIT 2**: One thing that caught my attention is the use of that makes it much faster than other choices when used as the modulo parameter in`pow()`

. It seems to be a difference of few seconds, in this case. By the way, it's still meaningless as I should not use such a modulo in the intermediate steps. To really get this problem through I believe it is not required to get the original terms in the first place.

Sort 6 Discussions, By:

Please Login in order to post a comment