10689 - Yet another Number Sequence

davor · Post by **davor** » Thu Aug 12, 2004 3:17 pm

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?

Larry · Post by **Larry** » Thu Aug 12, 2004 4:18 pm

It's not quite the same.. what changes did you make?

Minilek · Post by **Minilek** » Thu Aug 12, 2004 4:41 pm

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

.. · Post by .. » Thu Aug 12, 2004 9:40 pm

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

IIUC GOLD · Post by **IIUC GOLD** » Sat Aug 14, 2004 3:37 pm

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

natalya · Post by **natalya** » Sun Aug 15, 2004 8:02 am

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-

Minilek · Post by **Minilek** » Mon Aug 16, 2004 3:09 am

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.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Mon Aug 16, 2004 3:57 am

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.

Minilek · Post by **Minilek** » Mon Aug 16, 2004 6:18 am

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.

abishek · Post by **abishek** » Mon Aug 16, 2004 7:51 am

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.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Mon Aug 16, 2004 9:58 am

My definition of "the best" is the easiest to code (even from scratch, as the method is very simple), yet fast enough.

Per · Post by **Per** » Mon Aug 16, 2004 10:45 am

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)

Krzysztof Duleba · Post by **Krzysztof Duleba** » Mon Aug 16, 2004 1:17 pm

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.

IIUC GOLD · Post by **IIUC GOLD** » Mon Aug 16, 2004 3:49 pm

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.

natalya · Post by **natalya** » Mon Aug 16, 2004 5:40 pm

got AC, thanks.