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