FIBEASY - Editorial

editorial
, , , ,
45

you were right!!
my problem was with the log function.
my idea was almost same as the editorial except i didn’t use the periodicity part…
i observed a relation among the numbers

1 Like
46

@as_max_rider Well its good that you figure it out. :slight_smile:

47

hey everyone. cant i avoid TLE using this method i have done?

https://www.codechef.com/viewsolution/27348754

48

Hi,

I am seriously facing trouble understanding that. Can anybody give me an easy explanation.

49

Or handily you can avoid any sort of log function - use the bit_length() function of int class.

1 Like
50

my code nXxuep - Online C++ Compiler & Debugging Tool - Ideone.com
is partially correct, is it wrong to use log2(n) for large inputs…?
Thanks in advance…!

51

This solution seems to give 0 for the testcase:

1
84

In general, it’s a bad idea to use floating point where an integer solution is expected (though it’s OK sometimes e.g. sqrt when testing for primality, etc). People have come up with testcases where the use of log gives the wrong answer for FIBEASY - see e.g. here and the post linked from that post.

1 Like
52

Why website shows runtime error of problem code fibeasy?
#include<stdio.h>

int main(){
int T, N, j;
int f[50];
int first = 0,second = 1;
f[0] = first;
f[1] = second;
scanf("%d",&T);
while(T–){
scanf("%d",&N);
for(int i=2;i<N;i++){
f[i] = first + second;
first = second;
second = f[i];
}
}
for(int i=0;i<N;i++)
f[i] = f[i]%10;
while(N){
j=0;
for(int i=1;i<N;i=i+2){
f[j] = f[i];
j++;
}
N = N/2;
}
printf("%d",f[N]);
}

54

https://www.codechef.com/viewsolution/31854386
Can anybody review this solution of mine and tell me why is it showing TLE and how can i make it more efficient?

55

can anyone tell why my code (SEE THIS) is giving partially correct for subtask1 and wrong answer for subtask2

56

So we should basically know that fibonacci no.s mod 10 are periodic with period 60. So vague, isn’t it?
Or do they expect us to figure it out?

57

This :slight_smile:

1 Like
59

Well I read about Pisano period, its written that its not possible to manually calculate it for a given integer. (here)
Should we print the values and check ? Sounds very tedious and counterintuitive.

60

I can’t remember what I did - I either printed out the values, spotted the pattern and deduced why; or the other way around :slight_smile:

The logic behind it is fairly simple:

https://www.codechef.com/viewsolution/26609486

1 Like
61

Thanks a lot. U explained it in a nice way :smiley:

62

Can any body know that Fibonacci numbers mod 10 is periodic when they encounter the problem for the first time ?

63

I’m getting WA in subtask 2. I’m not getting what is wrong.
Here is my code
Any help would be appreciated.

64

FIBEASY - Editorial - #34 by ssjgz :slight_smile: