×

# TLE in MARRAY

 0 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: https://www.codechef.com/viewsolution/15900491 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 :D asked 19 Oct '17, 21:52 1 accept rate: 0% 15.5k●1●20●66

 0 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 answered 20 Oct '17, 23:45 4.0k●31●104 accept rate: 22%
 0 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. :) answered 21 Oct '17, 00:56 15.5k●1●20●66 accept rate: 18%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,738
×729
×140

question asked: 19 Oct '17, 21:52

question was seen: 270 times

last updated: 21 Oct '17, 00:56