test cases were weak
check the test case and solution given on this link
3 Likes
The input was not properly formatted. It cost me 3 penalties in python. I finally used int(raw_input()) instead of input() to scan integers and it got accepted 
9 Likes
Tester’s Solution uses a unsigned long long for a the number which is 1000 digits long!
Someone please explain how its working!
ALL SEE TESTER’s SOLUTION ONCE!
4 Likes
Cant understand how the tester’s solution works for big numbers…can any1 explain?
1 Like
Hello @all,
I too attempted to solve this question in Python using the idea described in the first paragraph of the editorial and got multiple NZEC and WA veredicts… And I have to admit that precomputing the values up to a large limit never occurred me during the contest…
Can anyone just clear me if the test cases were well designed and there are actually numbers with up to 1000 digits there?
Also, I’m assuming that the tester’s solutions works since it implicitly uses the property of when an overflow occurs the value is “automatically” wrapped around the range of an ULL and this would serve as a (possibly very cumbersome) hashing technique?
Because if such trick doesn’t apply here then something was definitely wrong with the test cases I think…
Best,
Bruno
We can simply generate O(D) fibonacci number and only restore the remainder of some relatively big number, for example, 2^64 or 10^9+7.
I don’t understand this part. Are we storing the Fibonacci numbers or number % 10^9 + 7 ?
The testcases are weak. People who did the problem with unsigned long long int also passed the testcases. Basically, according to the testcases, storing fibonacci numbers MOD 2^64 would have passed all the test cases !
2 Likes
@all : I am the setter for this problem .
You could generate all fibonacci numbers till 1000 digits ( no modulo is needed like the tester did ) and store them . The time limit and memory limit was conducive to do such a computation . You could store them in an array and do binary search for solving each query .
Or , otherwise you could use the fibonacci number property that 5nn + 4 or 5nn - 4 or both are perfect square to solve it . My solution ( setter’s solution ) uses it .
There were indeed test cases which had near about 1000 digits .
3 Likes
What’ the problem with my solution??? It was not accepted but I compared the output with others solutions which are accepted. I took large numbers (like 354224848179261915075 fib(100)) also… My code works fine… but when I submitted,its giving wrong answer… CodeChef: Practical coding for everyone… Please help me…
My solution is perfect… I ran the tester’s solution and it starts generating wrong fibonacci numbers after F(94)… So my solution was not get accepted… Tester’s F(95) - 1293530146158671551… My F(95) - 19740274219868223167…
@all : Tester is not storing big numbers . He is storing number mod 2^64-1 . Since numbers overflow by themselves he is not doing modulo operation . While this approach may pass , this cannot guarantee correctness , and I am not surprised that it fails some of the test cases that users are talking about .
4 Likes
@kurumua : I made the problem statement and test cases . The tester wrote and submitted his code after the test cases were posted . I discussed with the tester that “hashing” on any particular “modulus” can’t guarantee correctness . However since the output for the test cases was generated by my solution , the correctness was guaranteed . And we could not have prevented all possible “modulus” for hash from passing the test cases .
@kuruma : I agree that giving the “hashing” based solution to “editorialist” as a reference solution is highly misleading especially beginners . If you want you can write to codechef admin’s at bugs@codechef.com to get the “tester’s” solution replaced . I had already raised this issue during the problem setting process .
2 Likes
@vineetpaliwal, thanks for your reply and cofirmation 
I will definitely e-mail codechef admins regarding this matter as soon as possible for me 
By the way, the problem was interesting and your idea for solving it was also very good
Best,
Bruno
1 Like
I ran the tester’s code on my system, I am very sad to see that the output is ‘YES’ for all numbers greater than 10^64 
1 Like
Please tell, how is checkSquare() method implemented in author’s solution? Which formulae is used to check whether a number is perfect square or not? Any link/information will be highly appreciated.
Thanks
here is simplest solution by RAJAT De
hi here is a simple code
#include <stdio.h>
#include <string.h>
#include<iostream>
using namespace std;
long long c(char *s){
long long i,n=0;
for(i=0;i<strlen(s);i++)
n=10*n+s[i]-'0';
return n;
}
int main()
{
int t;
cin>>t;
while(t--)
{
long long a[6000],i,m;
char s[1001];
cin>>s;
m=c(s);
a[0]=1;a[1]=1;
for(i=2;i<6000;i++){
a[i]=a[i-1]+a[i-2];
if(a[i]==m){
cout<<"YES"<<endl;
break;
}
if(i==5999){
cout<<"NO"<<endl;
}
}
}
return 0;
}
HAPPY CODING
can anyone explain how it does work with long string
hey,can anyone tell me the error in the code, i am using property 5nn + 4 or 5nn - 4 or both are perfect square to solve it .CodeChef: Practical coding for everyone…
For those who are saying this question was biased towards JAVA, Well then I solved this problem in C++ in 5 minutes CodeChef: Practical coding for everyone and make sure you save my template so that you can do the BIGINTEGER stuff in c++ using strings.
@sikander_nsit, questions are not language dependent, some languages have advantages over others depending on the case. Competitors will always try and take advantage of their languages features.
1 Like