Page 1 of 1

11582 - Colossal Fibonacci Numbers!

Posted: Thu Feb 26, 2009 8:22 pm
by vahid sanei
I get Wrong answer :(
here is mycode :

Code: Select all

Accepted

Re: 11582 - Colossal Fibonacci Numbers!

Posted: Thu Feb 26, 2009 10:14 pm
by Jan
Check the case.

Input:

Code: Select all

126 121 111
Output:

Code: Select all

33
Hope it helps.

Re: 11582 - Colossal Fibonacci Numbers!

Posted: Fri Feb 27, 2009 8:16 am
by tryit1
i got accepted by a lame method.
How did you find the period ? Found on net that period has to be less than 6*n. So generated upton 12*n and checked for repetition of first 10 numbers.
Anyone used floyd.

vahid, you are doing it wrong. a^b %n != a^b % p where p is the period, it could be within p<=6*n, source wikipedia

Re: 11582 - Colossal Fibonacci Numbers!

Posted: Fri Feb 27, 2009 8:17 am
by vahid sanei
thanks Jan but i dont have idea for solving that :-?
could u give me some hints ?

Re: 11582 - Colossal Fibonacci Numbers!

Posted: Fri Feb 27, 2009 8:19 am
by vahid sanei
Thanks tryit , i try it :wink:

Re: 11582 - Colossal Fibonacci Numbers!

Posted: Fri Feb 27, 2009 10:46 am
by sohel
tryit1 wrote:i got accepted by a lame method.
How did you find the period ? Found on net that period has to be less than 6*n. So generated upton 12*n and checked for repetition of first 10 numbers.
Anyone used floyd.
It seems the the series returns back to 0 1 1 ... for every value of n.
I didn't know about the 6*n figure, so I just kept on inserting new values until a 0 is followed by 1.

Re: 11582 - Colossal Fibonacci Numbers!

Posted: Fri Feb 27, 2009 12:44 pm
by tryit1
Yes it returns backs to 0 1 1 .. But that observation can mislead. From your AC solution looks like it doesn't in this case.

If we are given a sequence of numbers like 0,1,1,2,3,5,6,7,0,1,1,2,0,1,1,2,3,5,6,7,0,1,1,2

how do you find the period of this ? Any thing easier than KMP.

If the values were unique could we apply floyd cycle finding. Can we modify it for the above sequence ? i tried but when there are duplicate values it breaks.

I guess there should be some algorithm which finds the period of a repeating sequence much easily.

Re: 11582 - Colossal Fibonacci Numbers!

Posted: Fri Feb 27, 2009 12:58 pm
by Jan
tryit1 wrote:Yes it returns backs to 0 1 1 .. But that observation can mislead. From your AC solution looks like it doesn't in this case.

If we are given a sequence of numbers like 0,1,1,2,3,5,6,7,0,1,1,2,0,1,1,2,3,5,6,7,0,1,1,2

how do you find the period of this ? Any thing easier than KMP.

If the values were unique could we apply floyd cycle finding. Can we modify it for the above sequence ? i tried but when there are duplicate values it breaks.

I guess there should be some algorithm which finds the period of a repeating sequence much easily.
I haven't understood fully. Its a Fibonacci sequence. So, you cant find a sequence that you have mentioned. However, suppose the sequence is based on any other criteria. Then stl map (or a bst) is a solution to your problem, too. Of course if the number of states is small.

Re: 11582 - Colossal Fibonacci Numbers!

Posted: Fri Feb 27, 2009 1:35 pm
by tryit1
You and sohel are right. It is a fibonacci sequence , so a first occurance of 0,1 starting with index > 2 solves the problem..My bad