pranay2063's blog

FIBOSQRT SPOJ
By pranay2063, 9 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Have you checked for n = 0 and n = 1 ? Your code gives wrong answer for these tests.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply