1

Eu estou há alguns dias tentando resolver um problema de programação que envolve buscas para encontrar a união e a intersecção entre conjuntos.

Eu consegui resolver o problema com pequenos conjuntos, porém quando o conjunto começa a ficar muito grande, por mais que programa chegue na resposta, eu recebo um "Time limit exceeded".

Eu fiz um programa semelhante em c++ e o código foi aceito, mas em python simplesmente não passou...

Eu otimizei o meu programa o máximo possível, porém o tempo de execução não mudou o suficiente...

Minha dúvida é:

  • Existe maneiras para reduzir ainda mais o tempo de execução com programas em python?

O problema se resume em dado uma quantidade de conjuntos. Por exemplo

Conjunto 1: -> 1 1

Conjunto 2: -> 2 1 5

Conjunto 3: -> 3 2 4 6

Conjunto 4: -> 4 1 3 5 7

E dado certas operações entre conjuntos retorne:

(1: Quantidade de elementos distintos da intersecção)

(2: Quantidade de elementos distintos da união)

Exemplo de operações:

Caso 1: -> 1 1 2 (Interseção entre conjunto 1 e conjunto 2)

Caso 2: -> 2 1 4 (União entre conjunto 1 e conjunto 4)

Caso 3: -> 1 3 4 (Interseção entre conjunto 3 e conjunto 4)

Caso 4: -> 2 2 4 (União entre conjunto 2 e conjunto 4)

Programa que fiz:

def main():
    # Casos de Teste
    for i in range(int(input())):

        lis = []
        # Quantidade de Conjuntos
        for j in range(int(input())):
            # Lista com todos os números do conjunto
            lis.append(list(map(int, input().split())))

            # O primeiro elemento é a quantidade de números do 
            conjunto
            lis[j].pop(0)

        # Quantidade de operçãoes
        for j in range(int(input())):
            # Operação e conjuntos escolhidos
            op, l1, l2 = map(int, input().split())

            # Interseção
            if(op == 1):
                # -1 por conta do index da lista
                inte = set(lis[l1-1]) & set(lis[l2-1])
                print(len(inte))

            # União
            else:
                union = set(lis[l1-1]) | set(lis[l2-1])
                print(len(union))

if __name__ == "__main__":
    main()

O link para a questão é: https://www.urionlinejudge.com.br/judge/pt/problems/view/2222

inserir a descrição da imagem aqui

0

1 Resposta 1

1

Enviei o seu código como python 3 e ele foi aceito sem nenhuma modificação... Veja abaixo captura de tela do resultado:

URI Online Judge

Fiz uma versão que ficou um pouco mais rápido que a sua; Para economizar tempo não converti os números para inteiro, e já gerei conjuntos diretamente (sem listas intermediárias):

T = int(input()) # Quantidade de instancias
for num_instancia in range(T):
    N = int(input()) # Quantidade de conjuntos
    conjuntos = {str(num_conjunto+1): set(input().split()[1:])
        for num_conjunto in range(N)} # le os conjuntos
    Q = int(input()) # quantas operacoes
    for n_op in range(Q):
        tipo, conj1, conj2 = input().split() # le a operacao
        if tipo == '1': # intersecao
            print(len(conjuntos[conj1] & conjuntos[conj2]))
        elif tipo == '2': # uniao
            print(len(conjuntos[conj1] | conjuntos[conj2]))

Resultado:

resultado 2

2
  • Que estranho... Eu tentei aqui novamente e recebi runtime error... Mas o seu programa passou. 27/12/2018 às 16:35
  • @DurvalCarvalhodeSouza Runtime Error não é relativo ao tempo que demorou para executar... É diferente de timeout; Significa que deve ter alguma coisa errada no seu código; Por exemplo, o comentário "O primeiro elemento é a quantidade de números do conjunto" deve estar em uma linha só;
    – nosklo
    27/12/2018 às 17:08

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .