10689 - Yet another Number Sequence

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

davor
New poster
Posts: 8
Joined: Sat Jun 28, 2003 11:04 pm

10689 - Yet another Number Sequence

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

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

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

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

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.......
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

IIUC GOLD
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Location: Bangladesh
Contact:

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
New poster
Posts: 3
Joined: Sun Aug 15, 2004 7:55 am

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-
Last edited by natalya on Mon Aug 16, 2004 5:39 pm, edited 1 time in total.
Go Natalya!

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

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
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

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.

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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)

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

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
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Location: Bangladesh
Contact:

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
New poster
Posts: 3
Joined: Sun Aug 15, 2004 7:55 am

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

got AC, thanks. :oops: :oops:
Go Natalya!

Post Reply

Return to “Volume 106 (10600-10699)”