CODEWITHSUNDEEP
pythonalgorithmoptimizationdata-structures
RajkumarG
RajkumarG

Reputation: 146

Optimizing the run time of the nested for loop

I am just getting started with competitive programming and after writing the solution to certain problem i got the error of RUNTIME exceeded.

max( | a [ i ] - a [ j ] | + | i - j | )

Where a is a list of elements and i,j are index i need to get the max() of the above expression.

Here is a short but complete code snippet.

t = int(input()) # Number of test cases
for i in range(t):
    n = int(input()) #size of list
    a = list(map(int, str(input()).split())) # getting space separated input
    res = []
    for s in range(n): # These two loops are increasing the run-time
        for d in range(n):
            res.append(abs(a[s] - a[d]) + abs(s - d))
    print(max(res))

Input File This link may expire(Hope it works)

Run-time on leader-board for C language is 5sec and that for Python is 35sec while this code takes 80sec.

It is an online judge so independent on machine.numpy is not available.

Please keep it simple i am new to python.

Thanks for reading.

Upvotes: 0

Views: 204

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58221

For a given j<=i, |a[i]-a[j]|+|i-j| = max(a[i]-a[j]+i-j, a[j]-a[i]+i-j).

Thus for a given i, the value of j<=i that maximizes |a[i]-a[j]|+|i-j| is either the j that maximizes a[j]-j or the j that minimizes a[j]+j.

Both these values can be computed as you run along the array, giving a simple O(n) algorithm:

def maxdiff(xs):
    mp = mn = xs[0]
    best = 0
    for i, x in enumerate(xs):
        mp = max(mp, x-i)
        mn = min(mn, x+i)
        best = max(best, x+i-mn, -x+i+mp)
    return best

And here's some simple testing against a naive but obviously correct algorithm:

def maxdiff_naive(xs):
    best = 0
    for i in xrange(len(xs)):
        for j in xrange(i+1):
            best = max(best, abs(xs[i]-xs[j]) + abs(i-j))
    return best

import random

for _ in xrange(500):
    r = [random.randrange(1000) for _ in xrange(50)]
    md1 = maxdiff(r)
    md2 = maxdiff_naive(r)
    if md1 != md2:
        print "%d != %d\n%s" % (md1, md2, r)
        exit

It takes a fraction of a second to run maxdiff on an array of size 10^5, which is significantly better than your reported leaderboard scores.

Upvotes: 1

alexis
alexis

Reputation: 50190

"Competitive programming" is not about saving a few milliseconds by using a different kind of loop; it's about being smart about how you approach a problem, and then implementing the solution efficiently.

Still, one thing that jumps out is that you are wasting time building a list only to scan it to find the max. Your double loop can be transformed to the following (ignoring other possible improvements):

print(max(abs(a[s] - a[d]) + abs(s - d) for s in range(n) for d in range(n)))

But that's small fry. Worry about your algorithm first, and then turn to even obvious time-wasters like this. You can cut the number of comparisons to half, as @Brett showed you, but I would first study the problem and ask myself: Do I really need to calculate this quantity n^2 times, or even 0.5*n^2 times? That's how you get the times down, not by shaving off milliseconds.

Upvotes: 1

Related Questions