You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

amartya_bhatt's gravatar image

1★amartya_bhatt
1
accept rate: 0%

converted to question 20 Oct '17, 01:09

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066


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

link

answered 20 Oct '17, 23:45

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

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

link

answered 21 Oct '17, 00:56

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 21 Oct '17, 00:56

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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