3
\$\begingroup\$

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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ for large size N and Q the following code exceeds the time limit - let's say N and Q equal to 200000 (fitting your constraints). What "time limit" is exceeded AND with that, why do you suspend the flow with input() on each iteration? \$\endgroup\$ Commented Oct 29, 2019 at 20:57
  • 4
    \$\begingroup\$ @RomanPerekhrest time-limit-exceeded is a rather common thing with programming challenges. I'd challenge OP's "other than changing the algorithm" though, because these challenges are often designed such that a naive algorithm fails the time constraint. \$\endgroup\$ Commented Oct 29, 2019 at 23:56

2 Answers 2

Reset to default
6
\$\begingroup\$

Code Review

PEP 8

PEP 8 recommends snake_case for variable names, so N, Q, A, L, R, and D all violate the guidelines.

A space should be used around operators: index - 1 and R - 1

Unused variables

N and testcase are never used, so should be replaced with the throwaway _ variable.

Variable naming

N, Q, A, L, R, and D are all "almost meaningless". Yes, they are directly from the problem description, but you could do better naming them array_size, num_queries, array, left, right and difference.

Is count_length a count of lengths? Doesn't seem to be; it is more like a max_length.

Is count_temp a count of temporaries? Or is it more like a segment_length?

_, num_queries = [int(x) for x in input().split()] array = list(map(int, input().split())) for _ in range(num_queries): left, right, difference = [int(x) for x in input().split()] if left == right: print("1") continue max_length = 0 segment_length = 0 for index in range(left, right): if array[index] == array[index - 1] + difference: segment_length += 1 if index == right - 1: segment_length += 1 max_length = max(max_length, segment_length) else: segment_length += 1 # to include the first element of AP max_length = max(max_length, segment_length) segment_length = 0 print(max_length)

Optimization

Without changing the Algorithm???

Ok, you're looking for just key-hole level optimizations. Let's see what we can do.

 for index in range(left, right): if array[index] == array[index - 1] + difference: ... else: ...

The above is inefficient code. Indexing into a list takes time, and you are doing it twice. Moreover, subtraction by 1 takes time, and it was to get the value which was looked up on the previous iteration!

Compare the above code with:

 prev = array[left - 1] for curr in array[left:right]: if curr == prev + difference: ... else: ... prev = curr

The indexing has been replaced with iteration over an array slice, and the current value from one iteration is carried forward to as the previous value in the next iteration. That should be a win, performance wise.

 segment_length = 0 for ...: if ...: ... if ...: segment_length += 1 max_length = max(max_length, segment_length) else: segment_length += 1 # to include the first element of AP max_length = ... segment_length = 0

Why are you starting the count from 0? That means you need this segment_length += 1 to account for that first element all the time. If you initialized segment_length = 1, you can skip that adjustment statement every time you reach the end of an arithmetic progression, saving another wee bit of time:

 segment_length = 1 for ...: if ...: ... if ...: max_length = max(max_length, segment_length) else: max_length = ... segment_length = 1

Finally, the code I hate the most:

 for index in range(left, right): if ...: ... if index == right - 1: ... else: ... ...

When does the for loop end? After index loops the final time with index = right - 1, of course. So the only time this if condition will be true is during the last iteration of the loop. During all of the remaining loop iterations, you are wasting time, subtraction 1 from right and comparing the result to index, when it can't possibly ever be true. Simply move the code to follow the loop.

_, num_queries = [int(x) for x in input().split()] array = list(map(int, input().split())) for _ in range(num_queries): left, right, difference = [int(x) for x in input().split()] if left == right: print("1") continue max_length = 0 segment_length = 1 prev = array[left - 1] for curr in array[left:right]: if curr == prev + difference: segment_length += 1 else: max_length = max(max_length, segment_length) segment_length = 1 prev = curr max_length = max(max_length, segment_length) print(max_length)

With changing the Algorithm

You explicitly requested optimization without changing the algorithm, so I'll leave you to discover where there is an algorithmic improvement to be made.

\$\endgroup\$
3
  • \$\begingroup\$ Not sure if for curr in array[left:right] is actually faster here than iterating over the indices, since it creates a copy of the slice each time. If right - left is large, this might actually make it slower. Would need some timings to be sure though. \$\endgroup\$ Commented Oct 30, 2019 at 9:08
  • 1
    \$\begingroup\$ @Graipher It is subtle, but the OP is (an)using Python’s exclusive range end-point to “do the right thing”. The problem description’s 1-based addressing and Python’s range(L, R) excluding R result in index - 1 going from L-1 to R-2 and index going from L to R-1, which is the proper Pythonic 0-based indices for comparing successive pairs. \$\endgroup\$ Commented Oct 30, 2019 at 13:39
  • 1
    \$\begingroup\$ @Graipher First test case returned 2 because I forgot the prev = curr line when transcribing code review changes into the final code-edit. My bad. \$\endgroup\$ Commented Oct 30, 2019 at 15:14
3
\$\begingroup\$

Just for fun I tried implementing this using just generators and the itertools. Using this has the advantage that you don't have to pay the price for indexing multiple times (like in your code), but also not the price for copying the slices (like in @AJNeufeld's solution). It also means that instead of using an array, this function can deal with A being a generator (but of course in that case you could not make multiple queries on the same array).

  • To get the range from the array, we can use itertools.islice, which works similarly to normal slicing (but without indexing from the end, because generators can be infinite).

  • Finding the difference between elements is straight-forward when iterating over pairs of elements, which you can get with itertools.tee and advancing one of the resulting iterators.

  • Finally, we need to run-length-encode the result and find the largest one where the chain of differences is the given difference. For this we can use itertools.groupby.

def graipher(array, left, right, difference): if left == right: return 1 it = islice(iter(array), left - 1, right + 1) it1, it2 = tee(it) next(it1) differences = (a - b for a, b in zip(it1, it2)) rle = (len(list(g)) for d, g in groupby(differences) if d == difference) try: return max(rle) + 1 except ValueError: # empty sequence, none of the differences is correct return 1

Note that I put this code into a function that returns the result, instead of printing it. This makes it reusable, and testable. When doing the same to the other solutions, we can even compare the performance using some random test data:

enter image description here

For small slices (R - L small) this generator approach is the slowest of the three approaches, whereas for larger slices it is the second fastest. AJNeufeld's approach is consistently the fastest, tested up to \$10^6\$ in slice length, which is a magnitude larger than the constraints given in the problem description.

Nevertheless, all three solutions use inherently the same algorithm, iterating through all elements in the slice, and therefore have the same asymptotic behavior.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.