Блог пользователя pranay2063

Автор pranay2063, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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?

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.