FIBEASY - Editorial

editorial
, , , ,
31

i also think the same, i think apart from the solution , its more challenging for a beginner to understand what mathematical concepts have been used , the editorial maker directly uses the various maths concept and make it harder , for beginners like me to understand .

so i think they should , go with more simpler approach to explain the logic.

32

another alternative is to use log2l instead of log2
It worked for me

1 Like
33

Receiving RE for the third input. I have tried so many approaches but still issue persists.


import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int t;
		int f[] = {0,1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,0,9,9,8,7,5,2,7,9,6,5,1,6,7,3,0,3,3,6,9,5,4,9,3,2,5,7,2,9,1};
		Scanner in = new Scanner(System.in);
		t = in.nextInt();
		while(t>0)
		{
		    long n,i;
		    i = 1;
		    n = in.nextInt();
		    while(i<=n)
		    {
		        i = i*2;
		    }
		    i = i/2;
		    i=(i-1)%60;
		System.out.println(f[(int)i]);
		t--;
		}
	}```
Is there any way we can find where im getting RE?
34

Please format your code - the forum software has mangled it and it is no longer valid Java! :slight_smile:

Edit:

Try the testcase

1
576460752303423487
1 Like
35

Thanks, prblem is with the way Im reading the input. changed “nextInt()” to “nextLong()” and it worked fine.

1 Like
36

This will help you alot : Easy Fibonacci | September long challenge 2019 | Codechef Solutions & Code || FIBEASY | Hello World - YouTube
see this thank you

37

this will help you a lot :
Just Go through This

Please Subscribe my channel Hello World .

3 Likes
38

where am i going wrong?

39

arr =[0,1]
for x in range(60-2):
arr.append((arr[-1]+arr[-2])%10)

def red(arr,n):
brr = arr[:n]
while(len(brr)!=1):
brr = brr[1::2]
return brr[0]

tc = int(input())
for i in range(tc):
num = int(input())
print(red(arr,num%60))

plss tell me where its exceeding time limit

40

Can someone point out the error in my code?

import java.util.*;
class Fibnocci {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int t,n,ans;
		ArrayList<Integer>a = new ArrayList<Integer>();
		ArrayList<Integer>e = new ArrayList<Integer>();
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		while(t>0){
			n = sc.nextInt();
			a.add(0);
			a.add(1);
			for(int i=2;i<n;i++){
				a.add(a.get(i-1)+a.get(i-2));
			}
			for(int i=0;i<n;i++){
				a.set(i, a.get(i)%10);
			}
			if(a.get(a.size()-1)==1){
				while(a.size()>1){
					for(int i=0;i<a.size();i++){
						
							if(i%2==0){
								a.set(i,-1);
							}
					}
					for(int i=0;i<a.size();i++){
						if(a.get(i)==-1){
							a.remove(i);
						}
					}
				}	
			}		
			ans=a.get(0);
			System.out.println(ans);
			t--;
		}
	}
}
41

For people who need more clear explanation of the editorial can go to the GitHub link: Easy Fibonacci

43

can anyone check why i am getting wrong answer on this::
double n = in.readDouble();
int x = (int)(Math.log(n) /
Math.log(2));
x = (int)Math.pow(2, x);
out.printLine(fib(x-1)%10);
out.flush();
//fib(x-1) is implemented in logn using matrix expo

44

@as_max_rider You can check your program output for the following test-cases:
4
9
72057594037927935
72057594037927936
18014398509481983

Output shoud be:
3
3
0
9

If your program is not giving the correct answer then read the editorial: Easy Fibonacci
Probably there is problem with how you are calculating log. Does your log function gives correct answers for large values.

NOTE: You don’t need to use matrix exponentiation.
You can also read the following post: FIBEASY Matrix Exponentiation Solution? O(lgn) (edit: this solution failed for subcase 3 Yet I am producing right answers?) - #3 by striker22

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