time limit exceeded......how to overcome this

general
1

my code is for ques code chn08
import java.util.Scanner;
public class chn08
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
long t = sc.nextLong();
for(long i=0;i<t;i++)
{
long a = 0; long b=0; long n=0;long z=0;
a = sc.nextLong();
b = sc.nextLong();
n= sc.nextLong();
for(long k=3;k<=n;k++)
{ z=b-a;
a=b;
b=z;
}
System.out.println(z%(1000000007));
}
sc.close();
}

}

2

The algo takes so much time to process, you have to improve time limit on server or in the code file. It happen to me too in adslvelocidad and i add more time to the server response and now works well when executing java or php files.

3

According to the given constraints, 1 <= T <= 10^{5} and 1 <= N <= 10^{9}. And, since you are using two nested loops, your algorithm has a complexity of \mathcal{O}(TN) = 10^{14} in the worst case. This is way too much for a time limit of 2 sec. Remember that you can only do about ~10^{8} operations in 1 sec.

Try to come up with a better approach. Write down the values of f(x) in terms of A and B for the first 10-12 terms and you will notice a repetition. The function f(x) is periodic with period 6, thus f(x) = f(x + 6). This way you can answer the queries in a single step.

1 Like