FIBEASY - Editorial

PROBLEM LINKS :

Contest : Division 1

Contest : Division 2

Practice

Setter : Kevin Matthew T

Tester : Istvan Nagy

Editorialist : Anand Jaisingh

DIFFICULTY :

Easy

PREREQUISITES :

Properties of Fibonacci Numbers, Bit Manipulation

PROBLEM :

After some deductions from a long statement, the problem is : Given a number N, we need to find the (X-1)^{th} Fibonacci number modulo 10, where X is 2^{MSB(N)}. Here, MSB(N) denotes the most significant bit of the number N.

QUICK EXPLANATION :

We can prove that for any sequence D_1,D_2,...,D_N which follows the nature given in the problem statement, the number remaining in the end is the number 2^{MSB(N)} where MSB(N) denotes the most significant bit of the number N. Additionally, we deduce that we need to calculate f(2^{MSB(N)} -1) \mod 10 , as the last digit of a number x is same as the number x \mod 10 . Finally, we shall use the property that the fibonacci numbers are periodic Modulo any given number.

EXPLANATION :

Terminology :

MSB(N) : It denotes the highest X, such that in the binary representation of the number N , the X^{th} bit is 1.

LSB(N) : It denotes the smallest X, such that in the binary representation of the number N , the X^{th} bit is 1.

Now, before moving to Fibonacci Numbers, let’s just first try and understand the behavior of the sequence D_1,D_2,....,D_N

Claim :

After i \ge 1 moves have been conducted over the sequence D, then the only numbers remaining are ones having their LSB \ge i

Proof :

In the first move, we exactly destroy all odd numbers, i.e. all numbers X, such that LSB(X)=0. In the second move, we destroy all numbers X, such that LSB(X)=1. As we go on, we can see that the only numbers remaining after the i^{th} move are the ones having LSB \ge i

Moving on,

Now, to reduce a sequence of N numbers D_1,D_2,...D_N to a sequence of size 1, it takes exactly \left\lfloor{\log_2{N}}\right\rfloor steps. But its quite simple to see that the number N is represented using \left\lfloor{\log_2{N}}\right\rfloor +1 bits.

So, after we’ve performed \left\lfloor{\log_2{N}}\right\rfloor steps, the size of the list should be 1, and we should have removed all numbers X, such that LSB(X) < \left\lfloor{\log_2{N}}\right\rfloor . Indeed, only 1 number \ge 1 and \le N satisfies the condition that its LSB \ge \left\lfloor{\log_2{N}}\right\rfloor , and that is the number 2^{MSB(N)}.

Now, moving to Fibonacci Numbers,

For any number X, its last digit is given by X \mod 10 . So, instead of considering that we are generating the sequence using the last digit and so on, in fact we can consider we just calculate the Fibonacci Numbers Modulo 10.

This gives us the the recurrence

f(0)=0,f(1)=1

f(i) = (f(i-1)+f(i-2)) \mod 10 , \hspace{0.2cm} i \ge 2

And since D_i = f(i-1) for i \ge 1 , we need to calculate f(2^{MSB(N)}-1) . Now to proceed further, we need to use a well known fact, which states that the Fibonacci Numbers are Periodic Modulo any given number, and in the case of the number 10, the period is 60.

This gives us, \forall \hspace{0.1cm} i \ge 60, f(i)=f(i-60), which in turn gives us :

f(i) = f(i \mod 60)

So, we can calculate the first 60 Fibonacci Numbers, everything Modulo 10, and then just print f((2^{MSB(N)}-1) \mod 60 ) .

That’s it, Thank you !

Your Comments are Welcome !

COMPLEXITY ANALYSIS :

Time Complexity : O(T \cdot \log(N) + Z) , where Z \approx 60
Space Complexity : O(Z), where Z \approx 60

SOLUTION LINKS :

Setter
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
 
// Kevin Mathew T
// Birla Institute of Technology, Mesra
// GitHub - https://github.com/KevinMathewT
// CodeForces - https://codeforces.com/profile/KevinMathew
// CodeChef - https://www.codechef.com/users/KevinMathew
// HackerRank - https://www.hackerrank.com/KevinMathew
// LinkedIn - https://www.linkedin.com/in/KevinMathewT
 
ll n, fib[100];
 
int main()
{
//	freopen("input.txt", "r", stdin);		//Comment
//	freopen("output.txt", "w", stdout);		//this out.
	ios::sync_with_stdio(false);			//Not
	cin.tie(NULL);							//this.
	cout.tie(0);							//or this.
 
	fib[0] = 0;
	fib[1] = 1;
 
	for(ll i=2;i<60;i++)
		fib[i] = fib[i-1] + fib[i-2];
	for(ll i=0;i<60;i++){
		fib[i] = fib[i] % 10;
	}
 
	ll T;
	cin >> T;
	while(T--){
		cin >> n;
		// ll t = n;
		// cin >> n;
		// n = (((ll) pow(2, (ll)log2(n))) - 1) % 60;
 
		ll pos = 0;
		while (n >>= 1) ++pos;
		// cout << pos << "--\n";
		n = ((ll) pow(2, pos) - 1) % 60;
 
		cout << fib[n] << "\n";
	}
 
	return 0;
} 
Tester
#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
 
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
 
using namespace std;
 
int main(int argc, char** argv)
{
#ifdef HOME
	if (IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	vector<int> fb(1050);
	int loopstart = 0, loopend = 0;
	fb[1] = 1;
	for (int i = 2; i < fb.size(); ++i)
	{
		fb[i] = (fb[i - 1] + fb[i - 2]) % 10;
		for (int j = 1; j < i; ++j)
		{
			if (fb[i] == fb[j] && fb[i - 1] == fb[j - 1])
			{
				loopend = i;
				loopstart = j;
				break;
			}
		}
		if (loopend)
			break;
	}
	int T;
	int64_t N, pw;
	scanf("%d", &T);
	for (int tc = 0; tc < T; ++tc)
	{
		scanf("%lld", &N);
		pw = 1;
		while (2 * pw <= N)
		{
			pw *= 2;
		}
		pw--;
		pw %= (loopend - loopstart);
		printf("%d\n", fb[pw]);
	}
	return 0;
}
Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh

#include<bits/stdc++.h>

using namespace std;

typedef complex<double> base;
typedef long double ld;
typedef long long ll;

#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
const int maxn=(int)(2e5+5);
const ll mod=(ll)(1e9+7);
int a[maxn];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    int t;cin>>t;

    while(t>0)
    {

        ll n;cin>>n;int high=-1;

        for(ll i=0;i<62;i++)
        {
            ll now=1ll<<i;

            if((n&now)!=0)
            {
                high=i;
            }
        }

        vector<int> v;v.resize(60);v[1]=1;

        for(int i=2;i<60;i++)
        {
            int now=(v[i-1]+v[i-2])%10;

            v[i]=now;
        }

        int zz=(1ll<<high)%60ll;

        cout<<v[zz-1]<<endl;

        t--;
    }

    return 0;
}
10 Likes

can somebody please say the test cases where my solution is failing?[https://www.codechef.com/viewsolution/26561501]

See this post.

1 Like

by the words of @kevinmathew try this

1
18014398509481983

output should be 9

3 Likes

thank you…:blush:had spent hours on it trying to debug it during the contest but to no good .

1 Like

This was my first contest and I was able to solve 2 questions.Is that a good thing?

3 Likes

It’s wonderful, as far as I can remember, in my second contest on CF, I couldn’t solve a single problem.

Thanks I am some what motivated now.

Do you know any books or websites for learning new topics I couldn’t solve GDSUB as it needed permutations and I forgot how to use it after boards.

In competitive programming, I don’t think books are a good way to go, It’s better to solve as many problems as you can

1 Like

Okay thanks for info.

Why does codechef have such a bad explanation technique? They have excellent resources when it comes to introduction to programming for school students but when it comes to editorial they severely lack quality. This is where they fall behind GeekForGeeks. I have solved this question during the long challenge but reading this editorial takes too much effort and even though the method used is same as mine, I couldn’t understand it at the first go. I request codechef to increase the simplicity in the editorial and come up with teaching techniques similiar to GeekForGeeks, Khan Academy or TedEd.

7 Likes

That is quite harsh. I tried to write a detailed editorial even though it’s the first problem in the contest. Can you let me know what Part of the editorial is lacking?

And, what makes you think one should always understand things in the first go?

2 Likes

I think it was an absolutely fine Editorial, and appreciate your efforts :slight_smile:

I think the only thing it needs is a quick, informal one-paragraph “Quick-Explanation” at the beginning; something like:

"The Fibonacci numbers Mod 10 repeat after a small initial sequence, so we can compute the i^\text{th} for large i quickly. The last element of D remaining when the process terminates will be the {2^j}^\text{th} of the initial elements of D, where j is the highest value with 2^j \le N".

Or something like that :slight_smile:

This is the approach @vijju123 takes, and it works very nicely.

3 Likes

Very good editorial. Especially loved the 2^MSB(N) proof part.

1 Like

If you see the pattern , answer for this is one of 0,1,2,3,9
N = NoOfBits(N). (ex: for 11 NoOfBits = 4)
N = 1 ans = 0
N = 2 ans = 1
N%4 = 0 => 3
N%4 = 1 => 0
N%4 = 2 => 9
N%4 = 3 => 2
Check this https://www.codechef.com/viewsolution/26556990

[ PYTHON3 SOLUTION ]
NOTE - Don’t use builtin “log” function, make your own custom function.
If you haven’t understand given editorial solution, you can try this - https://www.youtube.com/watch?v=YaKLCrm1oQA

My python solution - https://www.codechef.com/viewsolution/26650959

1 Like

This was my first time, participating in a competitive programming challenge. But I couldn’t even solve first easy problem.
Here’s what I did http://ideone.com/s3XYuw
But can’t figure out what went wrong.

@drkknt
It’s alright! Everyone starts somewhere :slightly_smiling_face:

And for your code! It looks like your logic is incorrect.
For every n, you need

x=power(2, floor(log2(n)))

and then output v[x%60-1]
Here implement log2 and power function by your own

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 : https://www.codechef.com/viewsolution/26405550

2 Likes