TLE in MARRAY

help
, ,
1

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)?

My solution link: CodeChef: Practical coding for everyone

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
    
t = int(sys.stdin.readline())

for _ in range (t):

    arrays, length = [], []
    n = int(sys.stdin.readline())
    maxlen = 0
    for __ in range (n):
        temp = list(map(int, sys.stdin.readline().split()))
        length.append(temp[0])
        maxlen = max(maxlen, temp[0])
        del temp[0]
        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 :smiley:

2

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

3

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. :slight_smile: