Sort 22 Discussions, By:
Please Login in order to post a comment
Sum of square of each number of an AP with first term a and common difference d, is given by
Σn^2(a,d) = n.(a^2)+(1/6).(d^2).n.(n-1).(2n-1)+a.n.d.(n-1) ; n is number of terms
So if you put a=1 and d=1
You get, Σn^2(1,1)
= (n/6).(6n+2.n^2 - 3n + 1)
= (n/6).(2.n^2 + 3n + 1)
Which is formula for Σn2.
So by using Σn^2(a,d) formula, we don’t need to get the sum using loop, we can directly get the sum of square of AP till nth term using this.
For example, In 3^2+5^2+7^2, a=3 and d=2 and n=3
So if we put it in above formula, we get 83.
Hope this will eliminate the timeouts, along with the fact that if sum of first 2 terms exceeds limit till you have to search palindrome(N), you should break the loop.
can you explain how did you get that formula? I have used this formula but still getting timeout on every testcase except the sample testcase.
You get the formula (or a similar one) if you type into Wolfram Alpha: sum((a+kd)^2,k=0..n)
I'm unable to understand your last statement.
"along with the fact that if sum of first 2 terms exceeds limit till you have to search palindrome(N), you should break the loop" ?
Are you following brute force approach to compute sigma(a^2(n,d)) for all possible combinations of a,n.
Or are you using some pruning strategry by prestoring all possible palindromes. and looking for few combinations for a,n that will get to the desired palindrome.
Thanks for the post.
You probably don't want to use that formula. You have to double-loop anyways, one for starting number, the other for # of terms. It's much faster to add on a j*j than to compute that summation formula.
This problem really only comes down to having a fast palindrome check.
Was passing with 100.00 with Pypy 2 but only 47.06 with Python 2. After all, there often exists a better approach than brute force.
Note - If a certain number can be written as the sum of consecutive squares in more than one ways, it must be counted ONLY once.
brute froce approach is not working it is showing TLE how can i optimize more , any suggestions ???
First Test Case executed Successfully but the others fail saying 'Timed Out'.
How do I Finish this?
Any Info could be helpfull.
Test for random cases till 10^9 and check if u get the right answer.Also try optimizing the loop's execution speed.
Lol Same Except first one all others failing....
i am getting wrong answer for test cases 29,31and 32 please help.thanks
whats is meant by timeout??? how to resolve that !! My testcases except testcase 0 is showing timeout.
Is it due to more time complexity of my code?
Yes, it is due to the time complexity of your code. All of the tests can be solved in <10s. If your code exceeds 10s on any testcase then it is aborted and considered a fail.
when my input is same i get right ans and then a zero
eg: 2 1000 1 1000 1
any idea why? thanks
Check if you initialize all the variables again in the second set, or there is some value that you keep between loops.
hi, i have tried all the test cases in the discussions and i get the right answers but my solution only works for the first and second hidden cases. please help!
I have passed all the testcase except 3-7 (wrong answer) and 10-12 (timeout)...
I have passed all the testcase except 3-7. Can anyone suggest where am I wrong??
I am getting wrong answer for all cases except first and last,and timeout error for testcase 8.works for sample case,works for 2 1000000000 1000000000 5 1 outputs 0 0.help?
At one point, I also had wrong answers for all cases except for the first and the last. For me, it was because I wasn't keeping track of the previously found sums. There are some consecutive squares that has the same answer. You shouldn't be adding the same number twice.
I have exactly the same problem. 3-7 fail. I have checked the bounds, used long ints and avoided duplicate palindromes, but still don't get these tests.