Sort 6 Discussions, By:
Please Login in order to post a 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.
Just in case it mights help someone :
1.all these are binomial coefficients.
2.for the god of pythons, dont do (-1)**3000
I cannot pass the test 8. Can anyone give some hints?
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.
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.