Codeforces 271D

codeforces.com/problemset/problem/271/D

Mi solución para este problema es usando trie. Al principio procesar la entrada en un arreglo para almacenar las letras que son buenas. A partir de ahí, enumerar cada substring y poner en un trie todos los que tengan no mas de k caracteres malos. Finalmente la solución es la cantidad de palabras insertadas en el trie.

Hay que tener en cuenta que si enumeramos los substrings en orden (todos los que comienzan en el primer caracter en orden ascendente por la cantidad de caracteres, luego todos los que comienzan en el segundo, etc), cada substring se obtiene agregando solo un caracter al final del anterior. Esto nos permite mantener la posicion en el trie, e insertar solo un caracter en vez de todo el substring, lo cual optimiza el algoritmo, ya que no tenemos que crear los substring, sino insertar solo un caracter en el trie. De forma similar, al encontrar mas de k caracteres malos, no tenemos que agregar mas caracteres a ese substring, sino movernos al próximo  Al insertar cada caracter en el trie, lo marcamos como terminal y si no estaba marcado anteriormente, incrementamos la cantidad de palabras en el trie.

Mi solucion en Codeforces codeforces.com/contest/271/submission/3110083

Referencias

Articulo sobre Trie

Anuncios

Comentar

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s