TOPIC

PROBLEM 1814 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Unknown replied 5 years ago

    Opa, desculpa, acabei me esquecendo. Consegui accepted. Sabia que o problema estava relacionado a grafos, tentei criar um algoritmo para resolver o problema, porém consegui apenas TLE(meu algoritmo resolvia em w(n!)). Pesquisei/Estudei um pouco mais e consegui o famoso AC.

    De qualquer forma, grato pela resposta.

  • testoTLE replied 5 years ago

    É por ai. Você sabe que esta tabela que você criou pode ser utilizada para representar um grafo com peso nas arestas? 1-Se sim, agora pense como unir todos os vértices com custo minímo. 2-Caso contrário estude o que é um grafo com peso nas arestas e volte para 1.

  • Unknown replied 5 years ago

    Encontrei o erro do meu algoritmo. Basicamente ele só calcula alguns caminhos possíveis e em alguns casos(os 10%) ele vai dar erro. Consegui pensar em um jeito de resolver meu problema mas é um pouco confuso e sequer consegui implementar, alguém pode me dar alguma dica de como resolver esse problema? Estou realmente preso nele. x.x

    Ps: O jeito que imaginei foi o seguinte -> Fazer uma tabela com todas os números de trocas necessárias(Ex: Palavra 1 para palavra 3 precisa trocar 2 vezes, Palavra 3 para palavra 4 precisa trocar 1 vezes... etc) e calcular todos as combinações de caminhos possíveis(Transforma palavra 1 em palavra 3, calcula troca e depois transforma palavra 3 em palavra 4.../Transforma 4 em 1 e depois 1 em 3.. etc). E então.. é por aqui ou tem jeito mais fácil?

    Grato!

  • Unknown replied 5 years ago

    def quantTroca(palavra1, palavra2, tamPalavras):
        cont = 0
        for i in range(len(palavra1)):
            if(palavra1[i] != palavra2[i]):
                cont += 1
    
        return cont
    
    def segundoMenor(vetor, jaTrocada, tamPalavras):
        menor = tamPalavras + 1
        indice = 0
        for i in range(len(vetor)):
            if(i not in jaTrocada and vetor[i] <= menor):
                menor = vetor[i]
                indice = i
        info = []
        info.append(menor) 
        info.append(indice)
        return info
    
    infoPalavras = raw_input().split();
    numPalavras = int(infoPalavras[0])
    tamPalavras = int(infoPalavras[1])
    contaInstancias = 0
    
    while(numPalavras != 0 and tamPalavras != 0):
        contaInstancias += 1
        vetorPalavras = []
        numTrocas = []
        jaTrocada = []
        menor = tamPalavras + 1;
        contaTroca = 0
    
        #Le as palavras
        for i in range(numPalavras):
            vetorPalavras.append(raw_input())
    
        #Faz uma tabela com o numero de trocas para cada palavra em relacao a outra
        for i in range(numPalavras):
            numTrocas.append([])
            for j in range(numPalavras):
                numTrocas[i].append(quantTroca(vetorPalavras[i], vetorPalavras[j], tamPalavras))        
    
        #calcula menor troca do primeiro indice
        if(numPalavras > 1):
            for j in range(1, numPalavras):
                if(numTrocas[0][j] < menor):
                    guardaMenor = j
                    menor = numTrocas[0][j]
    
            jaTrocada.append(0)
            jaTrocada.append(guardaMenor)
            contaTroca += menor
            i = 0
    
            #Vai pegando os segundos menores e selecionando a melhor troca possivel 
            while(len(jaTrocada) != numPalavras):
                infoPalavraIni = segundoMenor(numTrocas[i], jaTrocada, tamPalavras )
                infoPalavraTrocada =  segundoMenor(numTrocas[guardaMenor], jaTrocada, tamPalavras)
                if(infoPalavraIni[0] <= infoPalavraTrocada[0]):
                    guardaMenor = infoPalavraIni[1]
                    contaTroca += infoPalavraIni[0]
                else:
                    i = guardaMenor
                    guardaMenor = infoPalavraTrocada[1]
                    contaTroca += infoPalavraTrocada[0]
    
                jaTrocada.append(guardaMenor)
            print "Instancia %d" %  contaInstancias
            print "%d" % contaTroca
            print 
        else:
            print "Instancia %d" %  contaInstancias
            print 0
            print 
    
        infoPalavras = raw_input().split()
        numPalavras = int(infoPalavras[0])
        tamPalavras = int(infoPalavras[1])

    Alguem pode me ajudar? 10% WA. Grato

  • 🧙The Install Wizard 🧙 replied 5 years ago

    Nao é nivel 1. Existem problemas que usam o mesmo tema e são nível 5.

  • Rã Solo e o código em python replied 5 years ago

    Certeza que essa é uma questão nível 1 mesmo?

  • Thalyson Nepomuceno replied 6 years ago

    é mais ou menos assim... só olhe isso se tiver tentando por muito tempo :D ele vai querer memorizar as trocas que vai ter q fazer para transformar uma string em outra string. Assim ele quer saber o mínima de trocas que vai ter q memorizar pra transformar qualquer string em qualquer outra string.

  • André Simão replied 6 years ago

    Vc pode considerar como uma troca apenas quando tem duas cadeias iguais, por exemplo no segundo caso de teste:

    Início 1 troca 2 trocas 3 trocas 4 trocas

    AAAAA AAAAA AAAAA AAAAA AACAA ATATA ATCTA AACTA AACAA AACAA ATCTA ATCTA AACTA AACAA AACAA AACAA AACAA AACAA AACAA AACAA

    Da primeira troca para a segunda e da segunda para terceira, apenas 1 troca foi contada por vez e 2 linhas foram modificadas cada troca. Flws!

  • Diego 2.0 replied 6 years ago

    Estou com algumas dúvidas no problema. Não se se entendi muito bem os casos de teste, alguém poderia me explicar? =D Grato!!