 # TLE in MARRAY

OCTOBER LONG MARRAYS:
Can anyone help me saying why my code is giving TLE although I had memoized and I think it runs in O(n1+n2+n3)?

``````import sys

import math
memo = []

def taste(arrays, n, length, level, endidx):

if level == n: return 0

if memo[level][endidx] > -1:

#print(level, endidx, 'rerurned from memo')

return memo[level][endidx]

sum = 0

if level == 0:

for i in range (length[level]):
temp = taste(arrays, n, length, level + 1, (i-1)%length[level])
#memo[level][endidx] = temp
sum = max(sum, temp)
memo[level][endidx] = sum
#print(memo)
return sum
for i in range (length[level]):
#print('level = %d, length[level] = %d, endidx = %d, i = %d, (i - 1) mod length[level] = %d' %(level, length[level], endidx, i, (i - 1) % length[level]))

temp = abs(arrays[level - 1][endidx] - arrays[level][i]) * level + taste(arrays, n, length, level + 1, (i-1)%length[level])
#print(temp)
#memo[level][endidx] = temp
sum = max(sum, temp)
#print(sum)
memo[level][endidx] = sum
#print(memo)
return sum

for _ in range (t):

arrays, length = [], []
maxlen = 0
for __ in range (n):
length.append(temp)
maxlen = max(maxlen, temp)
del temp
arrays.append(temp)
#print(arrays)
memo = [[-1 for i in range (maxlen)] for j in range (n)]
#print(memo)
print(taste(arrays, n, length, 0, 0))
``````

Plz someone help me

And thanks in advance I’m not much in python, so i dont think I’ll be able to help debugging your solution, but i can share my approach at following link

https://discuss.codechef.com/questions/115030/a-simplified-approach-to-marrays

The problem had weak test data, thats why some similar brute force approaches passed.

From what I have seen, recursive version did not pass as recursion is costly. But iterative version for same passed, that too well within time limit. But that doesnt matter- neither of them are the intended solution.

From What I see in your code, you are also trying to solve this by memotization of previous values. Its not enough. Say, 2 dishes of 5 * {10}^{6} ingredients each. Your code with be O({N}^{2} for this test case. The reason why we can pass subtask 1 is because we can simply start with either the maximum or the minimum element for dish 1. But other scenarios with >1 dish will fail.

Try reading the official and unofficial editorials and grasp the real solution. After all, that is going to help you in long run. 