I have solved a question named NOMATCHES. It is showing TLE error after optimising the code as much as I can ,suggest me any way to solve this problem using python.
My code is :
from itertools import permutations as ps
import sys
f=[]
m=[]
t=int(input())
def fun(perm,n):
for i in perm:
for j in range(0,n-1,2):
m.append(i[j]-i[j+1])
s=sum(m)
f.append(s)
m.clear()
print(max(f))
#f.clear()
for i in range(t):
n=int(input())
a=list(map(int,sys.stdin.buffer.readline().split()))
perm=list(ps(a))
fun(perm,n)
what are the ways through which I can optimise my code to achieve the target.
If I am not wrong, the question code is NOMATCH.
And about the solution of the question, you are computing all permutations of the array. There will be N! permutations of the array. This will surely result into TLE.
Actual result is easier than it seems. To increase the absolute difference as stated in the question, you just need to add absolute differences of ith smallest and ith largest number from the array.
To do that you first need to sort the array, and then subtract A[i] from A[N-i], for each 1 <=i <= N/2 . Then add the absolute values of all subtractions. So time complexity will be O(NlogN+N) .
I hope I was able to explain the solution in the simplest way.
I am unable to write a code right now, but you can check this out. This is pretty straight forward solution that Samyak Jain has written.
1 Like