FIBEASY - Unofficial Editorial

PROBLEM LINK:

Contest
Practice

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Fibonacci Sequences.

PROBLEM:

Initially we are given an array A=[a_{1}, a_{2}, a_{3}....,a_{N}]. We are supposed to remove all elements occurring at odd indices in one step and we have to repeat this process until only single element remains. Let’s say we are left with some element a_{k}, so we need to output the last digit of the kth Fibonacci number.

STRATEGY

Fibonacci numbers follow the property : F'(N) = (F'(N-1) + F'(N-2)) \mod 10.
Here F'(N). represents the last digit of Nth fib number. Now if we look at the terms F'(N) is composed of, we can see that the pattern of F'(N) will start repeating at most after 10*10 terms, i.e we will get a cycle.
A simple trick to find when the cycle starts would be to find when again in the array the first and second terms consecutively appear. In our case here, cycle size = 60.
Now let’s get to the second part of the problem. Basically, we’re dividing our array A repeatedly by 2. So we can make an observation that the number which would be the highest power of 2 in the array would remain until the end.

FIBONACCI PATTERN

If we observe more closely, we can see that we’ll be only accessing these elements-
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048...
Since our cycle length is 60, we take the modulus of all these elements with 60 and we get-
1, 2, 4, 8, 16, 32, 4, 8, 16, 32, 4, 8...
We see that after the 1st and 2nd term, we have the repetition of 4th, 8th, 16th and 32nd term. So we only need to store these elements.

CODE

#include <iostream>
using namespace std;
typedef long long lld;

int log(lld N) {
    int count = 0;
    while (N) {
        N /= 2;
        count++;
    }
    return count-1;
}

int main() {

    // freopen("input.txt", "r", stdin);

    int T;
    scanf("%d", &T);
    
    int dp[] = {2, 3, 0, 9};

    while (T--) {
        lld N;
        scanf("%lld", &N);
        
        int max_power = log(N);
        if (N==1) {
            printf("0\n");
        } else if (N==2 || N==3) {
            printf("1\n");
        } else {
            printf("%d\n", dp[(max_power-2) % 4]);
        }
        
    }
    return 0;
}

TIME COMPLEXITY

Time complexity of the algorithm discussed in this editorial is O(lg(N)) per test case.

8 Likes

same approach i tried but getting wrong answer:smirk:
here is my solution.plz tell me my mistakes.
https://www.codechef.com/viewsolution/26305849

Can anyone please tell what may be the problem with this solution because it follows similar approach as in the editorial (apart from the last part) but it fails for large test case somehow -
https://www.codechef.com/viewsolution/26620164

Don’t use C++ inbuilt log as I guess it gives some floating point errors. Create your own function to calculate max power 2 term like the one shown in editorial

Dont use inbuilt log :stuck_out_tongue:

1 Like

awwwwwwwww maaaannn :sob::sob::sob: can’t belive lost 80 points coz of inbuilt function nonetheless thank you very much for pointing out the mistake.

Inbuilt log function returns float or double so for sufficiently large value the return value is an approximation and not an integer and that on conversion to integer might be less than 1 then the actual value.
http://www.cplusplus.com/reference/cmath/log2/

2 Likes

You can ultimately use the Fast Doubling Method to calculate Fibonacci Numbers under Modulo something in Log(N).

Solution using matrix exponential
https://www.codechef.com/viewsolution/26256246

2 Likes

:stuck_out_tongue_winking_eye::stuck_out_tongue_winking_eye::stuck_out_tongue_winking_eye:

1 Like

@gotham You seem to be a true programmer!! :sunglasses: Check this

6 Likes

Damn :joy::joy::joy:

2 Likes

my code is constantly showing runtime errors . i checked for the limits of vector i used for accessing the elements and found all of them fine i.e. i did not ask for any element beyond limit but it is still showing either SIGSEGV or SIGTSTP error. i am not able to find any other fault. one thing more, that, when i go for the custom input then it gives the correct output . kindly guide me to know the possible reason for this problem.

man you are legend:stuck_out_tongue_winking_eye::stuck_out_tongue_winking_eye:

I was almost near-see this https://www.codechef.com/viewsolution/26371693

that not his code though ! . who submmited that was a legend :laughing:

1 Like

can anybody help!!
i don’t understand what is wrong is this approach… keep showing WA… please help

import math
fib_cache={}
def fib(n):
    if n in fib_cache:
        return fib_cache[n]
    if n == 1:
        value = 0
    elif n==2:
        value = 1
    else: value = (fib(n-1)+fib(n-2))
    fib_cache[n]=value
    return value
try:
    test = int(input())
    for i in range(test):
        num=int(input())
        num=num%60
        x=math.floor(math.log2(num))
        print(fib(int(math.pow(2,x)))%10)

except:
    pass

I also type casted log and used it in my python code, and it gave me the same error,
Then i made the loop myself into a O(lgn) complexity one and submitted getting AC
I think for large values typecasting of log is somehow not giving the right response

thanks man, its good lesson to learn.

What’s wrong with this approach? I am passing one of test case of 30 points. But failing somewhere. My code is fast enough to not get TLE. Then whats wrong?
https://www.codechef.com/viewsolution/26575262