Page 1 of 2

10689 - Yet another Number Sequence

Posted: Thu Aug 12, 2004 3:17 pm
by davor
I getting WA with this problem but I think that my solution is OK.
My algorithm:
I use matrix chain multiplication.
I send my solution to p10229( Modular Fibonacci ) and I got Accepted.
Are there any tricks?

Posted: Thu Aug 12, 2004 4:18 pm
by Larry
It's not quite the same.. what changes did you make?

Posted: Thu Aug 12, 2004 4:41 pm
by Minilek
Hint: Coefficients -- F(0) = a
-------------
F(1) = 0a + b
F(2) = a+b
F(3) = a+2b
F(4) = 2a+3b
F(5) = 3a+5b

Fib(0,1,2...) = 0, 1, 1, 2, 3, 5

Posted: Thu Aug 12, 2004 9:40 pm
by ..
My case is, I used my old code from 10229, but keep getting WA.
At last, I found my code of 10229 is wrong, though it is accetped.......

Posted: Sat Aug 14, 2004 3:37 pm
by IIUC GOLD
If you know "Pisano period" then you can solve the problem very easily.

The last digit of Fibonacco number repeats with a period of 60. The last
two digits repeat with a period of 300, the last three with a period of
1500 and the last four digits have a period of 15000.

See the following link:
http://mathworld.wolfram.com/PisanoPeriod.html

Posted: Sun Aug 15, 2004 8:02 am
by natalya
i read your post, read about pisano period, and try to solve this problem, but always got WA. however i'm not sure is pisano period valid for all a and b (i mean f[0]=a, f[1]=b)? or just for a=0 & b=1?

Code: Select all

--cut---
thank you in advance.

-natalya-

Posted: Mon Aug 16, 2004 3:09 am
by Minilek
not valid for all (a,b) pairs. there's nothing profound about the number 15000; this number changes as a,b, or m changes.

i used this 'pisano period' method (but at the time i submitted didn't realize it was even called that until i see this thread now). just figure that the last m digits of fib(n-1),fib(n) determine the last m digits of fib(n+1), so the sequence has to be periodic with period at *most* 10^{2m}. i experimented to see what the period was for m = 10^4 and luckily it just happened to be 15,000 (instead of something like 10^8 which would have sucked :-? ).

the trick is realizing that (except for val[0]=a), val in your array can be expressed as p*a + q*b where p and q work out nicely. i used this to get ac in .037s. see my hint post above and hopefully you'll realize what i mean.

good luck.

Posted: Mon Aug 16, 2004 3:57 am
by Krzysztof Duleba
I find matrix method the best. Counting power of a proper 2x2 matrix allows to get n-th value of sequence f(n) = p * f(n - 1) + q * f(n - 2) for any p, q and for any starting value. I solved many problems doing copy-paste and simply changing the constants.

For the simple case here it's enough to find

Code: Select all

|a, b    |      *      |0, 1|^n mod m
|b, a + b|             |1, 1|
Of course to find the power one should use O(log n) algorithm.

Posted: Mon Aug 16, 2004 6:18 am
by Minilek
I find matrix method the best...
I think it depends what you mean by best. I used this first also because I already had it pre-coded from doing other fibonacci-type problems. But this method runs slower than the periodic method, and it is also more lines to code if you don't have it coded up already.

Posted: Mon Aug 16, 2004 7:51 am
by abishek
i find that if i implement the matrix as a class the number of lines of code is drastically reduced. the power of OOP and operator overloading is really nice, and it doesnot take up any more time than the bare minimum even in a contest.

Posted: Mon Aug 16, 2004 9:58 am
by Krzysztof Duleba
My definition of "the best" is the easiest to code (even from scratch, as the method is very simple), yet fast enough.

Posted: Mon Aug 16, 2004 10:45 am
by Per
In my opinion, the biggest strength of the matrix method compared to the period method is the asymptotic complexity. In this problem, the period was quite small, but the maximum moduli could just as easily have been set to say, 10^9, and the period method would never have worked. In order to make the matrix method inapplicable, you'll have to use Really Really Big(tm) values of n, which I doubt will happen in a contest problem.

(Nonetheless, this was actually the first problem where I used the matrix method for computing fibonacci numbers)

Posted: Mon Aug 16, 2004 1:17 pm
by Krzysztof Duleba
I think that for such Really Really Big(tm) values of n no other method would work neither.

As I said before, the algorithm much more general. For instance, I used the same class for 10655 and just changed few lines in main() function to adjust the template.

Posted: Mon Aug 16, 2004 3:49 pm
by IIUC GOLD
Natalya:

You did a very silly mistake.

Just check your code's output for the following input:

Code: Select all

1
10 12 1 1
I think now you will be able to find your fault.

Also note that Pisano period is valid for all a and b.

Posted: Mon Aug 16, 2004 5:40 pm
by natalya
got AC, thanks. :oops: :oops: