FIBEASY answer keeps showing TLE

help
1

This was my first attempt on codechef.
I have only coded in school before this. I can’t understand why I keep getting TLE in the FIBEASY question.
This is my code:

#include
using namespace std;

int main() {
// your code goes here
int k,n;
cin>>k;
while(k–)
{
cin>>n;
int p=0, q=1,i=0,a=1;
while(n)
{
n=n/2;
i++;
}
while(–i)
{
a*=2;
}
if(a==1)cout<<0;
else
{
while(a!=2)
{
a-=2;
p=((p%10)+(q%10))%10;
q=((p%10)+(q%10))%10;
}
cout<<q;
}
}
return 0;
}

I think the custom inputs I give give the correct answer.
PLEASE HELP!!

2

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

3

Because your code is wrong!!!

4

Ok, I found your submission myself.

Try the testcase:

1
1000000000000

and bear in mind that in this testcase, N is just 10^{12} - from the problem constraints, it can ask you for any N up to 10^{18}, and it can ask you 10^5 times for such huge N!

5

Thanks!!
I can see how my program is failing but am not able to fix it!! I am trying to reduce the run time of the program wherever I can but it still won’t run.
I have seen a few of the other submissions and some of them are replacing a with a%60. Can you explain how this works? And even after i tried this, although the run time has reduced, it still isn’t low enough.
This is the link to my new submission.https://www.codechef.com/viewsolution/27093275

1 Like
6

To be honest, I think FIBEASY is an unusually tricky problem for beginners: if you sort the problems by Accuracy Rate:

FIBEASY is quite near the lowest - I’d recommend trying some of the ones with a higher accuracy rate (as a rule of thumb: the higher the accuracy, the easier) to get your feet wet.

Anyway, you can check out the Editorial solution if you’re really stuck - it will explain everything you need to know. My own solution is also heavily-commented and explains all the logic in-depth.

3 Likes
7

Thanks!! This helped me a lot!
I think I have got most of the things right. My test inputs are giving the right answers and there is no time limit error. But it is showing that my answer is wrong. Can anyone tell me what is wrong with this code?
The link to the code is: https://www.codechef.com/viewsolution/27096847

8

The answer for

1
2147483648

should be 3.

Edit:

A better example:

1
61

(should be 9).

9

your code might be right but it is showing tle becoz your code has atime complexity of npower3
optimize it to lower one like nsquare or n
my code had time complexity of order n so my time taken was 0.03 sec but urs it took 1.01s

10

Oh you’re right! I fixed the problem.
Now my answer is partially correct and there is TLE in subtask 2 :frowning:
Does anyone know how to fix this?
https://www.codechef.com/viewsolution/27099567

1 Like
11

Consider the testcase:

1
1073741824
12

There is TLE error even in this testcase. I can’t figure out how to simplify the program any further:sweat_smile:
Is my program wrong or can it be simplified further? I can’t figure it out with this testcase.

13

Here’s a hint: that testcase doesn’t just make your program slow; it sends it into an infinite loop.

Try it out locally on your machine and use a debugger (or add in some debug output - but remember to remove it before submission!) to find out exactly what’s happening.

14

OHH!!! I got it!!! Thanks a lot!! You have been a huge help!!

1 Like
15

Good job; happy to help :slight_smile:

Here’s Manish’s working solution :slight_smile: CodeChef: Practical coding for everyone