FIBEASY - Editorial

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

2 Likes

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.

8 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?

4 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.

5 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 CodeChef: Practical coding for everyone

3 Likes

[ 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 - - YouTube

My python solution - CodeChef: Practical coding for everyone

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 s3XYuw - Online C++0x Compiler & Debugging Tool - Ideone.com
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 : 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.