0
\$\begingroup\$

hackerearth.com practice problem Can you solve it?:

Given an array 'A' consisting of 'n' integers, find the maximum value of the following expression: \$\lvert A_i - A_j\rvert + \lvert i - j\rvert\$

where \$A_i\$ is the element of the array at the i-th position (0-indexed array)

My solution:

def solve(n,l):
    ans=0
    for i in range(n):
        for j in range(n):
            if ans < (abs(l[i]-l[j])+abs(i-j)):
                ans=(abs(l[i]-l[j])+abs(i-j))
                print(ans)


t=int(input())
for _ in range(t):
    n=int(input())
    l = list(map(int,input().split()))
solve(n,l)    

This code passes all the sample test cases but when I finally submit the code
for two inputs it shows wrong and
for all the other inputs it shows time limit exceeded.

Kindly point out what is wrong and what can be done in order to get the correct output.

\$\endgroup\$
  • \$\begingroup\$ The description says to maximize the value, but the code looks like it is trying to find the minimum (if ans < (abs(l[i]-l[j])+abs(i-j))) \$\endgroup\$ – RootTwo Jan 21 at 3:11
  • \$\begingroup\$ (@RootTwo you seem to expect comparisons done current ? candidate, the code shows candidate < current.) \$\endgroup\$ – greybeard Jan 21 at 7:15
  • 2
    \$\begingroup\$ While advice about code giving results as specified, but failing to meet requirements in any other way is on topic, code giving wrong results is not ready for review at CodeReview@SE. \$\endgroup\$ – greybeard Jan 21 at 7:18
  • 2
    \$\begingroup\$ @MadhuraankB: Sorry, that was more bad luck that got you the right results. Make a number of inputs, and try them all. \$\endgroup\$ – David G. Jan 21 at 13:18
  • 1
    \$\begingroup\$ Welcome to Code Review! I'm afraid this question does not match what this site is about. Code Review is about improving existing, working code. Code Review is not the site to ask for help in fixing or changing what your code does. Once the code does what you want, we would love to help you do the same thing in a cleaner way! Please see our help center for more information. \$\endgroup\$ – Vogel612 Jan 21 at 14:17
2
\$\begingroup\$

The minor problem is that you are printing the result in the wrong place.

The major problem is that n may be up to 100,000. This means you need to run 10,000,000,000 of your inner test. And you may have only 0.02 seconds to do that.

The trick to dealing with that is probably to determine the maximum possible score of a given i and l[i], and skip the inner loop if it isn't worth it. As part of this, you might find it beneficial to determine the range of the l[] values.

As an example, if you determine that all l[i]<=5, then it isn't worth looking at i>6 and i<n-6 (or thereabouts... I'm not positive about the border condition).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Your last paragraph, where all l[i] are less than 6, isn't true if some l[i] is very negative, say -100. You need to find the smallest and largest values and take their difference. \$\endgroup\$ – Ray Butterworth Jan 21 at 3:53
  • \$\begingroup\$ @RayButterworth, True, but the full problem statement included: n up to 100,000, and l values from 0 to 100,000, up to 100 "problems" in the input, and a 2 second time limit. \$\endgroup\$ – David G. Jan 21 at 11:20
1
\$\begingroup\$

solve() shouldn't print anything, much less all the intermediate results. It should end with return ans and the main program should print that final result.

You'll get the same answer for (i,j) as for (j,i), so for the inner loop j never needs to be less than i.

The expression abs(l[i] - l[j]) + abs(i - j) gets calculated twice. Instead, assign the value to a temporary variable and use that twice.

David G.'s suggestion, of finding the maximum possible contribution of the l[i] - l[j] term and using that to restrict the range of i and j, is perhaps the most effective optimization.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ One can't simply restrict the range of i and j. One can determine that no j will produce a better score than the current best score. I'm not sure if this means you can restrict to j>i. \$\endgroup\$ – David G. Jan 21 at 11:23
  • \$\begingroup\$ @DavidG., say l[i]=X; l[j]=Y. If you compute |X-Y| + |i-j| you'll get the same value as when you compute |Y-X| + |j-i|, so there's no point in doing both calculations. The extra one can be avoided simply by assuming i ≤ j. \$\endgroup\$ – Ray Butterworth Jan 21 at 14:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.