Problem Link- https://www.hackerearth.com/challenges/competitive/october-circuits-19/algorithm/ap-1-f43562f4/
Problem Statement :
You are given an integer array of size A. You are also given queries Q. In each query, you are given three integers L, R, and D respectively.
You are required to determine the length of the largest contiguous segment in the indices range [L, R] of A that forms an arithmetic progression with a common difference of D
Note: The segment whose length is 1 always forms an arithmetic progression of a common difference D
Input format
First line: Two space-separated integers N and Q respectively Second line: N space-separated integers denoting elements of A Next Q lines: Three space-separated integers L, R, and D (1<= L <= R <= N) respectively
Output format
Print Q lines representing the answer such as the ith line denotes the answer for the ith query.
Constraints
1 <= N <= 200000 1 <= Ai <= 200000 -200000 <= D <= 200000
Sample Input
5 2 1 2 3 5 5 1 5 1 4 4 3 Sample Output 3 1
Explanation
For the first query, [1,2,3] forms an AP with difference 1.
For the second query, [5] forms an AP.
I was attempting to solve this problem on hacker earth, however for large size N and Q the following code exceeds the time limit. Is there any way I can make this code run faster, other than changing the algorithm?
N, Q = [int(x) for x in input().split()]
A = list(map(int, input().split()))
for testcase in range(Q):
L, R, D = [int(x) for x in input().split()]
if L == R:
print("1")
continue
count_length = 0
count_temp = 0
for index in range(L, R):
if A[index] == A[index-1] + D:
count_temp += 1
if index == R-1:
count_temp += 1
count_length = max(count_length, count_temp)
else:
count_temp += 1 # to include the first element of AP
count_length = max(count_length, count_temp)
count_temp = 0
print(count_length)
N
andQ
equal to200000
(fitting your constraints). What "time limit" is exceeded AND with that, why do you suspend the flow withinput()
on each iteration? \$\endgroup\$