[Python] Desafio Zé Coquinho do Beecrowd

Zé Coquinho é um artesão que produz esculturas feitas com cocos. Os cocos secos são cortados ao meio e as cuias formadas pelas cascas são pintadas e utilizadas para construir as esculturas. As esculturas são muito famosas, sendo procuradas por colecionadores de todo o mundo.

Figura 1: A mais famosa escultura de coco feita por Zé Coquinho.

As esculturas de Zé Coquinho são sequências de cuias coladas umas nas outras. Uma escultura bem-formada é definida pelo seguinte conjunto de regras:

Uma sequência vazia de cuias é uma escultura bem-formada. Se T é um escultura bem-formada, então uma escultura formada por (T) (ou seja, uma cuia aberta para a direita, seguida de T , seguida de uma cuia aberta para a esquerda) é uma escultura bem-formada; Se T e S são esculturas bem-formadas, então ST (ou seja, a escultura S seguida de T) é uma escultura bem-formada. Note que todas as esculturas bem-formadas são construídas usando apenas as regras descritas acima. Seja T uma escultura formada por cuias de coco. Se T não é uma escultura bem-formada, dizemos que T é uma escultura mal-formada.

Uma característica marcante das esculturas de Zé Coquinho é que elas nunca são bem-formadas; todas as esculturas que ele fez na sua longa vida são mal-formadas.

O Museu de Arte Moderna de Graviúna quer fazer uma exposição de esculturas de Zé Coquinho. Para organizar a exposição, o museu resolveu ordenar as esculturas em ordem lexicográfica. Na ordem lexicográfica definida pelo museu o símbolo ( vem antes do símbolo ). Por exemplo, ((( < (() e )( < )).

O comprimento de uma escultura mal-formada é o número de cuias que a mesma possui.

Dados dois inteiros N e K, você deve determinar a K-ésima escultura mal-formada de comprimento N considerando a ordem definida pelo museu. Considere que Zé Coquinho fez todas as esculturas mal-formadas de comprimento N.

Entrada A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.

A primeira (e única) linha de cada instância contém dois inteiros N e K, onde 1 ≤ N ≤ 50 e 1 ≤ K ≤ 2n − 1, indicando respectivamente o comprimento da escultura e o índice da escultura (na ordem lexicográfica) que você deve determinar.

Saída Para cada instância imprima uma linha contendo a K-ésima escultura mal-formada de comprimento N . Caso não exista uma tal escultura imprima uma linha contendo −1.

Exemplo de Entrada Exemplo de Saída 4

4 0

4 4

6 63

7 13

((((

())(

-1

((())()

Eu usei o seguinte código:

T = int(input())
resultados = []

for _ in range(T):
N, K = map(int, input().split())

sequencias = []
caracteres = ['(', ')']
pilha = ['']

while pilha:
atual = pilha.pop()
if len(atual) == N:
sequencias.append(atual)
else:
for caracter in caracteres:
pilha.append(atual + caracter)

# Verificar quais sequências são mal-formadas
sequencias_malformadas = []
for seq in sequencias:
balance = 0
malformada = False
for caracter in seq:
if caracter == '(':
balance += 1
else:
balance -= 1
if balance < 0:
malformada = True
break
if balance != 0:
malformada = True
if malformada:
sequencias_malformadas.append(seq)

sequencias_malformadas.sort()

# Verificar se a K-ésima sequência mal-formada existe
if K < len(sequencias_malformadas):
resultados.append(sequencias_malformadas[K])
else:
resultados.append("-1")

for resultado in resultados:
print(resultado)


E o tempo limite do desadio foi excedido. Tentei outra abordagem, mas não foi suficiente pra melhorar o desempenho:

from itertools import combinations

def eh_malformada(seq):
balance = 0
for char in seq:
if char == '(':
balance += 1
else:
balance -= 1
if balance < 0:
return True
return balance != 0

def encontrar_kesima_malformada(N, K):
if N % 2 != 0:
return "-1"

contador = 0
for bits in combinations(range(N), N // 2):
seq = [')'] * N
for i in bits:
seq = '('
seq = ''.join(seq)
if eh_malformada(seq):
if contador == K:
return seq
contador += 1
return "-1"

# Leitura da entrada
T = int(input())
for _ in range(T):
N, K = map(int, input().split())
print(encontrar_kesima_malformada(N, K))


Como eu faço para tornar esse código mais eficiente diminuindo o tempo de execução?

Continue reading...