I have an O(1) solution for each test case and there are a total of 10000 cases, still i am not able to figure out why am i getting a TLE. Here is the link CodeChef: Practical coding for everyone
.I have submitted 3-4 times and i can’t get anything faster than this. plz help
I am writing the same in python and will post here to tell how it goes.
the java one
import java.io.*;
class Main {
static int sum = 0;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(reader.readLine());
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < T; i++) {
String[] lo = reader.readLine().split(" ");
sum = 0;
long K = Long.parseLong(lo[0]);
int d0 = Integer.parseInt(lo[1]);
int d1 = Integer.parseInt(lo[2]);
int ind = solve(d0,d1);
if(ind>=K){
if(sum%3==0) writer.write(“YES”);
else writer.write((“NO”));
}
else{
int rem = (int) ((K-ind)%4);
rem = (rem==0||rem==2)?0:2;
int u = (int) ((2*((K-ind)>>2)%3)%3);
if((sum+u+rem)%3==0) writer.write(“YES”);
else writer.write(“NO”);
}
writer.newLine();
}
writer.flush();
}
private static int solve(int d0, int d1) {
sum = d0+d1;
int res = 2;
while(true){
int t = sum%10;
if(t==2) return res;
else{
res++;
sum+=t;
}
}
}
}
and here goes the python
def solve(a,b):
s = a+b
res = 2
while(True):
t=s%10
if(t==2):
return (res,s)
else:
res+=1
s+=t
t=int(input())
while(t):
t=t-1
K,d0,d1 = [int(x) for x in input().split()]
p = solve(d0,d1)
index_where_two_starts = p[0]
sumtillind = p[1]
if(index_where_two_starts>=K):
if(sumtillind%3==0):
print(“YES”)
else:
print(“NO”)
else:
rem = (K-index_where_two_starts)%4
if(rem==0 or rem==2):
rem=0
else:
rem=2
u = (2*((K-index_where_two_starts)>>2)%3)%3
if((sumtillind+u+rem)%3==0):
print(“YES”)
else:
print(“NO”)
both are running fast on my local machine , i suspect that my solve function is not terminating. (i have assumed i will always get a pattern 2486248624862486… in the number .