FIBEASY - Editorial

FOR PEOPLE GETTING WA IN SECOND SUBTASK :
This is due to precision of log2 function.
try putting 2^56-1 as input in your code . u will see it gives 56 instead of 55. so u just need to raise the log2 value obtained to get the number again and compare it with your original number . since , we took floor of the log value , the number obtained by raising the log2 value must me smaller than original number ( or equal ) , if it is not just decrement your log2 value obtained by 1.
Refer this : CodeChef: Practical coding for everyone

3 Likes

Nothing to be ashamed of.
A lesson to be learned, if a solution involving built in function works for small numbers but fails on larger numbers, suspect the built in function!

I cant solve this problem even if I solved DOOFST :frowning:

1 Like

Thank you :slight_smile: @s5960r

Can anyone help, i am getting WA for large inputs

#include<bits/stdc++.h>
#include
#define ll long long
using namespace std;

ll power(ll x, ll y, ll mod){

ll result = 1;
x = x % mod;

while(y > 0){
if(y&1){
result = (result x)%mod;
}
x = (x
x)%mod;
y = y>>1;
}
return result;
}

int main(){

ll t; cin>>t;
int first = 0, second = 1, third;
vector series;
series.push_back(first);
series.push_back(second);

third = first+second;
first = second;
second = third;
series.push_back(third);

while(true){

first = second%10;
second = third%10;

if(first == 0  && second == 1){
    break;
 }

third = (first+second)%10;
series.push_back(third);

}

ll len = series.size()-2;

/*for(int i=0;i<series.size();i++){
cout<<series[i]<<" ";
}
cout<<endl;

cout<<"LEN "<<len<<endl; */

while(t–){

ll n; cin>>n;
ll a = floor(log2(n));
ll term = power(2,a,len);

//cout<<"TERM "<<term<<endl;

cout<<series[term-1]<<endl;

}

return 0;
}

1 Like

Check cp-algorithms.com it’s a good starting point

1 Like

this is link to my solution CodeChef: Practical coding for everyone i used the logic that unit digit of fibonacci repeats after 60 digits and the selected element in array can be represented as a[2^n-1].
please tell me if code could be improved in some way

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.

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

1 Like

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?

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

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

1 Like

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

this will help you a lot :
Just Go through This

Please Subscribe my channel Hello World .

3 Likes

where am i going wrong?

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

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--;
		}
	}
}

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

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