PKU 1451 - T9

Autor da análise: RicardohahnRicardohahn

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1451

Resumo

Dado o dicionário, a freqüência das palavras e as teclas pressionadas pelo usuário no teclado numérico do celular, o problema pede, a cada tecla apertada, o prefixo mais provável que a seqüência de números significa.
A freqüência de cada prefixo é a soma das freqüências das palavras que contêm esse prefixo.

Solução

Precisamos então, para cada prefixo da seqüência de teclas da entrada, calcular qual é o prefixo que tem maior freqüência.
Isso pode ser feito utilizando-se de uma árvore de prefixos, onde em cada nó guardamos a freqüência dele (e do prefixo definido por ele, conseqüentemente) e se ele é um nó terminal (ie, uma palava termina nele).

Precisamos agora de um modo de para cada prefixo numérico admitido, saber qual o prefixo alfabético de maior freqüência correspondente. Para isso usaremos uma árvore de prefixos, mas dessa vez suas arestas representam números e não letras como no caso anterior. E seus vértices guardam qual o prefixo de freqüência máxima para ele e a freqüência de tal prefixo.
Desse modo, basta ir percorrendo essa árvore com a string numérica de entrada que a cada nó (vértice) teremos a string a ser impressa na saída.

Agora falta o mais importante, como inicializar essas estruturas, porque se elas satisfazerem essas propriedades (principalmente a árvore numérica) o problema estará resolvido.

Na hora de inserir uma palavra, temos como atualizar instantaneamente a freqüência de cada prefixo, pois basta adicionar a freqüência da palavra a cada nó inserido.
Enquanto estamos inserindo uma palavra na árvore de letras, podemos simultaneamente percorrer a árvore numérica, com os números correspondentes às letras. Com isso a cada nó, temos a freqüência do prefixo dele, e se ela for maior que a do prefixo numérico, então devemos atualizar a string guardada nesse nó para o prefixo (alfabético) atual e atualizar sua freqüência.

Desse modo obtemos as duas estruturas citadas anteriormente e para dar a resposta basta ir percorrendo a árvore com os números da entrada. Se não houver nó ou aresta correspondente à entrada, deve-se imprimir "MANUALLY".

Para implementar essas estruturas eu defini structs que contém as arestas para os próximos nós e as outras propriedades.
Essa árvore não é completa, então o número de nós efetivamente usados é muito menor que todos os possíveis, o que nós faz implementar essa árvore de forma semelhante a um grafo comum (e não como um heap).

A complexidade do algoritmo é $$O(w \cdot l^2)$$ (w é o número de palavras e l é o tamanho máximo de cada palavra), mas na média esse algoritmo é muito mais rápido, pois esse pior caso ocorre somente quando todas as letras inseridas modificam o prefixo ótimo.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License