Pensei um pouco sobre alguns problemas recentemente e decidi fazer um editorial que pode ser útil caso alguém tivesse dificuldade em fazê-los depois. Para começar, escolhi dois problemas do URI Online Judge (que, na verdade, são originais de provas da maratona de programação ACM ICPC):
URI 1231: Palavras (link para o problema)
URI 1265: DJ da Computação (link para o problema)
O primeiro é interessante. Para o primeiro caso, há solução simples:
Podemos dividir essa solução em etapas diferentes, que são independentes e que chamamos de "estados". Cada transição de estado é única e não pode ser repetida.
Com a 1ª letra da 1ª palavra do conjunto 1, podemos emparelhar a 1ª palavra do conjunto 2. Dizemos que a letra que estamos tentando emparelhar (começamos desta letra, no caso), é o nosso estado. A seta representa uma mudança de estado.
OK, esta é a única mudança possível, mas quando emparelhamos o 0 ainda restam letras desemparelhadas. No caso, é a 2ª letra da 1ª palavra do conjunto 1. Novamente temos uma transição possível e a letra desemparelhada passa a estar no conjunto 2. As transições possíveis do conjunto 2 são:
Repetimos o procedimento até não restar letras desemparelhadas (existem palavras em comum) ou esgotar todas as transições (não existem).
Se existissem mais de uma transição possível, testaríamos todas até alguma funcionar ou acabarem as possibilidades. Para achar as transições, basta pré-computar (implementando de qualquer jeito passa no tempo).
A parte importante é que as transições não devem ser repetidas. Não faz sentido testar um emparelhamento testado antes, já que eles são independentes e vamos voltar para uma situação anterior.
PS: 'Cat' é categoria (que foi inventada aqui). 'N.E.' é o número de elementos na categoria (em cat = 1, cada elemento tem 1 letra, em cat = 2, cada tem 2...). 'Tam' é o número total de letras. Tam = N.E. * Cat.
Ou seja, dada a posição de um elemento, podemos saber em que "categoria", ele está inserido, basta ir subtraindo aos poucos o total de elementos das categorias anteriores. (Em outras palavras, se 'Tamanho da string' - 3 > 0, não está em Cat 1. Se 'Tamanho da string' - 3 - 3*3*2 > 0, não está nem em 1 nem em 2. Se 'Tamanho da string' - 3 - 3*3*2 - 3*3*3*3 > 0..., até descobrir em qual está).
Ou seja, dada a posição de um elemento, podemos saber em que "categoria", ele está inserido, basta ir subtraindo aos poucos o total de elementos das categorias anteriores. (Em outras palavras, se 'Tamanho da string' - 3 > 0, não está em Cat 1. Se 'Tamanho da string' - 3 - 3*3*2 > 0, não está nem em 1 nem em 2. Se 'Tamanho da string' - 3 - 3*3*2 - 3*3*3*3 > 0..., até descobrir em qual está).
Para saber quem é quem na própria categoria, dá para olhar por subgrupo de "cat" elementos e em cada subgrupo, há um padrão de repetição (em cat = 2, para cada palavra de 2 letras da forma XY, Y segue o padrão ABCABCABC e X segue AAABBBCCC, em cat = 3, para cada palavra de 3 letras da forma XYZ, Z = ABCABC... , Y = AAABBBCCCAAA... e X = A (9 x) B (9 x) e C (9 x) ).
Leão, poderia dar uma explicada melhor no problema "Palavras"? Não entendi muito bem o por que isso vai dar certo.
ResponderExcluirFala Thalyson! Valeu pelo feedback, vou tentar ser mais claro. Imagina como se fosse um grafo e eu estou fazendo uma DFS. Meu objetivo é chegar em alguma coisa do tipo 0100 emparelhando com 100. Esse emparelhamento (tinha chamado de transição) dá certo, então se eu chegar nessa transição, beleza, posso retornar que deu certo para os caras que estavam checando isso (se for recursivo, por exemplo).
ExcluirAgora supõe que eu tô combinando 010 com 100 (combinando a partir do 1). Se eu combinei uma vez, para frente é um subproblema. Não faz sentido eu tentar combinar de novo (vou estar em um loop). Supõe que eu prossigo nessa combinação e não chego em lugar nenhum (retorno falso). Eu volto na minha DFS. Mas se eu chegar nessa combinação pegando outro caminho, eu já sei que ela é ruim, porque já fui por esse caminho antes.
Então só faz sentido testar cada combinação uma vez. Eventualmente elas vão se esgotar. Deu pra enteder melhor ou ainda tá meio obscuro? Se eu falhei na lógica pode me falar também.
Este comentário foi removido pelo autor.
ExcluirEu só conseguir entender depois que o fonseca me deu um hit. Ele explicou praticamente a mesma coisa, mas com outras palavras.
ExcluirA ideia é fazer uma dfs(ou bfs) com uma pd(para n ficar repetindo estados) tentando chegar ai palavra vazia a partir das palavras de um conjunto no outro.
Vlw Matheus, tava tentando fazer essa a muito tempo xD (e depois que você faz, fica parecendo tão fácil, codei em uns 5-10min depois da tua explicação mais o hit do fonseca '-')
Show! Vou continuar tentando escrever sobre alguns problemas pra ver se pego a prática, sou fã de quem faz isso, mas realmente é um pouco difícil. Depois que eu escrevo eu vejo os erros e a confusão hehe, Qualquer coisa que eu puder ajudar tamo aí :)
ExcluirEu já pensei q fazer o mesmo, mas só escrevi sobre um problema e parei xD
ExcluirAlgum dia eu retorno nisso. Penso em fazer isso, principalmente, por que normalmente minhas soluções são bem diferentes das oficiais xD
Porém um grande problema é a escrita. De como passar, pois quem procura editoriais quer as coisas o mais resumido possível. Ai fica difícil.
Boa sorte :D