Hi all, i have been trying to solve this problem: http://www.spoj.com/problems/FIBOSQRT/
It is given that
1)F(n)=F(n-1)+F(n-2) with F(0)=0 and F(1)=1
2)Fs(n)=Fs(n-1)+Fs(n-2)+2*SQRT(3+Fs(n-1)*Fs(n-2)) with Fs(0) and Fs(1) are given in the input file.
What i am doing is : Let K(n) = sqrt(3 + F(n-1) F(n-2)). Then, after applying some mathematics , we get K(n) = F(n-2) + K(n-1). I got the idea from : http://www.quora.com/How-can-the-problem-FIBOSQRT-of-SPOJ-be-solved
After that, i tried to find the the matrix for the recurrence relation which i got as: matrix [3][3]={{1,1,0},{2,1,1},{0,1,0}};
After multiplying it for (n-1) times, i multiplied it by {K(2),f[1],f[0]} and calculated the result.
Here is my code: http://ideone.com/4ho8nX
I am getting correct answer for most of the cases but getting wrong answer everytime. It would be very helpful if anyone provides even slight help/correction.
If your program is giving right answers for most test cases (I don't know how you determined that, but you can tell by writing a brute-force solution and checking your output against it on some random small cases), it's really helpful to look for boundary tests. What happens if one of the inputs has the highest possible value? Or the lowest?
As per your suggestion,i made a brute force tester program. But, how can i test highest possible value such as n=10^18 which is difficult to be done through brute force?
For large n, you just want to make sure that you don't get overflows or accesses past the end of arrays or stuff like that. For this you can just read your code to see if you have these issues.
But your problem in this case are actually small n (namely n=0 and n=1).
Have you checked for n = 0 and n = 1 ? Your code gives wrong answer for these tests.
Some experience with SPOJ tells me that each submission is always tested on every testcase for the task (it means that you can see your program fail on something like 50th test... but it may have failed on the second or third one).
That's why you shouldn't take into account the fact that your submission was evaluated quite long.