TOPIC

Python - Time Limit Exceeded

Bruno Reis asked 3 years ago

Pessoal, gostaria de saber como poderia otimizar meu código para que não dê conflito com o tempo mínimo de execução. Qualquer ajuda seria muito bem vinda!

x=y=p=1
while(x != 0 or y != 0 or p != 0):
    #Inputs
    x,y,p = list(map(int,input().split()))

    if (x==0 and y==0 and p ==0):
        break

    q = int(input())

    #Montando lista das mensagens de Conan
    mensagem = []

    for i in range(q):
        inputs = input().split()

        #Convetendo para int os valores de entrada da área do terreno
        inputs = [inputs[0]] + list(map(int,inputs[1::]))

        #Ordenando valores de xy - zw
        for i in range(len(inputs)):
            if(inputs[0] == 'P' and inputs[1] > inputs[3]):
                x = inputs[3]
                inputs[3] = inputs[1]
                inputs[1] = x
            if(inputs[0] == 'P' and inputs[2] > inputs[4]):
                x = inputs[4]
                inputs[4] = inputs[2]
                inputs[2] = x

        mensagem.append(inputs)

    #Montando lista de pragas e suas posições, além dos questionamentos de gastos
    encontradas = ii = 0
    for i in range(len(mensagem)):   
        if(mensagem[i][0] == 'P'):
            while(ii < i):
                if mensagem[ii][0] == 'A' and \
                   mensagem[ii][2] >= mensagem[i][1] and \
                   mensagem[ii][3] >= mensagem[i][2] and \
                   mensagem[ii][2] <= mensagem[i][3] and \
                   mensagem[ii][3] <= mensagem[i][4]:
                    encontradas += mensagem[ii][1]
                ii+=1
            ii = 0
            print(encontradas * p)
            encontradas = 0

Acredito não haver nenhum erro de lógica, pois está funcionando com diversas entradas diferentes, inclusivo com a do exemplo... O problema mesmo está no tempo de execução, que parece exceder o mínimo desejado. Obrigado!

Remember not post solutions. Your post may be reviewed by our moderators.

  • Diego Rangel replied 3 years ago

    Não tenho certeza se essa é a única forma, mas por exemplo a complexidade iterando normalmente sobre matriz seria O(N x M), N - linhas, M - colunas, no pior caso. Além disso, existem Q consultas, logo a complexidade seria O(Q x N x M). Na pior situação teriamos N = 10³, M = 10³ e Q = 10⁵ logo a complexidade seria O(10⁵ x 10³ x 10³) = O(10¹¹) que dá TLE sem dúvidas. Já usando uma BIT 2D a complexidade seria O(Q x log(N x M)) logo, seria O(10⁵ x log(10³ x 10³)) ~ O(6 10⁵) que passa de boas. :D Se eu estiver certo sobre as complexidades !

  • Bruno Reis replied 3 years ago

    Somente assim será possível obter o tempo mínimo com python? Pois o algoritmo que criei ja soluciona a problema, mas gostaria de otimizá-lo sem mudar totalmente sua estrutura...

  • Diego Rangel replied 3 years ago

    Esse problema precisa se resolvido usando uma BIT 2D.