UVa 12526

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

Cellphone Typing (http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3971)

Problema

Dado um dicionário de palavras, deseja-se encontrar o custo médio de digitá-las sabendo que existe um auto completar que preenche parte da palavra sempre que possível.

Observações

O número de caracteres dado na entrada é até $10^6$. A solução deve ser linear ou próximo disso.

Dicas

  • Use uma árvore de prefixos para armazenar o dicionário.
  • Basta uma busca na árvore construída que se obtêm o custo médio.
  • Lembre-se de que o auto completar nunca preenche a primeira letra da palavra. Logo sua busca deve tratar o caso especial na raíz da árvore.

Solução

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Primeiramente deve-se construir uma estrutura de Trie. Depois, queremos encontrar o custo de todos os caminhos na árvore que cheguem aos vértices terminais (onde uma palavra termina). Seja $v$ um nó na árvore, $T$ o conjunto de nós terminais e $N(v)$ o número de filhos de $v$. Criamos então $Time(v, cost)$ que é o custo de todos os caminhos até terminais que estão depois de $v$ e $cost$ é o custo para chegar até o nó $v$.
  • $Time(v, 0) = \sum_{i=0}^{N(v)} Time(p_i, 1)$ com $p_i$ filho de $v$ e $v$ é a raíz da árvore.
  • $Time(v, cost) = cost$ se $v \in T$ e $N(v)$ é igual a zero.
  • $Time(v, cost) = \sum_{i=0}^{N(v)} Time(p_i, cost+(|N(v)|==1?0:1))$ com $p_i$ filho de $v$.

O primeiro caso trata quando $v$ é a raíz da árvore. O segundo caso é quando chegamos a uma folha da árvore, logo o $cost$ é o custo o qual queremos encontrar. O terceiro caso ele incrementa o custo somente se $v$ possui mais de um filho, caso contrário o auto completar irá escrever aquele caracter automaticamente. A resposta para esta questão é $Time(v, 0)/numeroPalavras$ com $v$ sendo a raíz da Trie.

Implementação

As dicas de implementação ficam ocultas por padrão. Desencorajamos que você as olhe antes de ter tentado.
Para melhorar a eficiência, não é necessário usar alocação dinâmica nesta questão. Como o tamanho máximo de todo o dicionário é $10^6$, logo pode criar uma estrutura parecida com:
struct trie{
   int nodes[1000000][26];
   int size;

   trie(){
      size = 0;
      fill(nodes[0], nodes[0]+26, -1);
   }origem

   void add(string s){
   }
};

A matriz $nodes_{i, j}$ armazena o nó filho do i-ésimo nó com a j-ésima letra do alfabeto. O valor -1 indica que não há adjacência. Pode-se também criar um vetor indicando nós terminais.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas