Cant seem to get whats wrong with the solution…I even used an alternative for the inbuilt log function…still subtask 2 failed.
Solution Link:CodeChef: Practical coding for everyone
Check out the constraints. N can take the value up to 10^18 and you are looping over it inside the fib function. That’s why you are getting the wrong answer. If you carefully see and check it will create the pattern for the nos. 3 onwards. The pattern will be 3,0,9,2 for every no. I am adding my soln. here if you want to check. CodeChef: Practical coding for everyone Feel free to share your thoughts and doubts too. Happy coding !!
his solution is correct , the verdict should be TLE but they showed WA.
No you also have to check the indexing of the array. The array with indexing up to 10^18 is not at all possible. Maximum memory you can allocate for the array is around 10^8 and that too globally.
we know that . where did he allocated ?? have you seen his code?
I was right @kaka420 solution using inbuilt pow function gives tle . i had modified your code calculation by making own pow funtion using binary exponentiation . Modified AC code - CodeChef: Practical coding for everyone.
1 Like
As @syntaxhacker said that the power function without binary exponentiation should give TLE, so I wrote power function taking O(N) time instead of O(log(N)) but still got AC.
CodeChef: Practical coding for everyone.
Also,@ kaka420 why have you written i<=n at line 12 ? .Since u are passing an array of 60 digits, fib[n] i.e fib[60] may give segfault. Idk why it still worked.
Also I noticed countbase function gives wrong ans for input 10^19 (although it has noting to do with your WA) even though 10^19 is in long long range.
bro input constraint is upto 10^{18}
Just an observation. Countbase gives ans 62 for input 10^19, but it should give 63. It doesn’t work being in long long int range.
fib() called inside findlastdigit() with size 60 
Yeah but within the constraint it shouldn’t give WA.
i<n is correct.That was me messing up the cycle of 60.
can you point it out
It is probably the log2() function. It is rounding off to a different value for higher integers.
can you give a test case
I also tried an alternative on Python 3.6 . But it showed WA as well probably due to the log() function.Is the log() method broken for all languages? xD
Solution Link: CodeChef: Practical coding for everyone
No it’s simply the log2 function.
https://www.codechef.com/viewsolution/26497393
My AC Solution using inbuilt power function. I just made my log2 function
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.
If floored value is the answer, then log2() always gives answer more than that floored value,isn’t it?. We need to find a case where log2() is approximating to a value less than actual floored log value.