2826 - No Spaces

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 9 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

2826 - No Spaces

Post by ymondelo20 » 6 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

HaZard
Posts: 114
Joined: 6 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 2826 - No Spaces

Post by HaZard » 6 years ago

saludos, alguien puede decirme porqué este código me da MLE:

Code: Select all

???
Last edited by HaZard on Fri Dec 19, 2014 5:17 pm, edited 2 times in total.
teruel

humbertodiaz
Posts: 97
Joined: 6 years ago
Gender: None specified

Re: 2826 - No Spaces

Post by humbertodiaz » 6 years ago

HaZard wrote:saludos, alguien puede decirme porqué este código me da MLE:

Code: Select all

???
Si la solucion funciona despues de esta discusion, por favor edita tu mensaje para que no quede una solucion casi-AC expuesta al mundo. =)

Veo varias posibilidades...

Es posible que un veredicto de MLE sea un efecto secundario de las pruebas que Jasr esta haciendo con COJ. No pude encontrar ningunos defectos en tu programa excepto que quizas estas excediendo los limites de memoria de verdad. Lo que me esta confundiendo es que tu solucion es bien similar a la mia, asi que en teoria la mia deberia haber fallado con el mismo error. Digamos que un autor cruel decide generar el peor caso posible que consume la mayor cantidad de memoria. Por que todos sabemos que los autores de ejercicios son crueles por naturaleza. ;)

Para eso, tendriamos que recibir una lista de palabras que maximiza cuantos nodos se deben crear en el trie. Eso envuelve crear palabras que son lo mas distintas posibles. Los primeros caracteres de las palabras inevitablemente seran compartidos dado que solo hay 26 letras disponibles. Sin embargo, las primeras 4 letras tienen suficientes combinaciones para cubrir las 10^5 palabras, por que podemos crear 26^4 = 456,976 prefijos distintos. Entonces las demas letras podrian ser aleatorias despues de ese punto, o podrian ser duplicadas como "aaa...aaa" para las 16 letras. No importa mucho ese detalle.

Tu solucion crea un nodo por cada letra. Asumiendo que recibimos 10^5 palabras distintas, con prefijos unicos, todos los nodos desde la cuarta letra en adelante pueden corresponder a una sola palabra. Por lo tanto, se crean 10^5 * (20 - 4 + 1) = 1,700,000 nodos para las ultimas letras. Mas estan los nodos de los niveles iniciales del arbol: (1 + 26 + 26^2 + 26^3) = 18,279. En total, podrian haber hasta 1,718,279 nodos.

Ahora la vulnerabilidad en tu diseño. Nota que por cada nodo que creas, inmediatamente se crea un arreglo de 27 punteros a hijos. Entonces tienes 27 * 1,718,279 = 46,393,533 punteros en total. Un puntero puede ocupar 4 bytes u 8 bytes, dependiendo de la arquitectura que corre el juez. En el mejor caso, los punteros ocupan 185,574,132 bytes. La conversion a MB no es tan clara por que depende - MB deberia ser 10^6 bytes, pero en algunos contextos es 2^20 bytes. En el mejor caso, tenemos que 1 MB = 2^20 bytes. Pues... tu programa consume casi 177 MB nada mas en punteros. El limite para este ejercicio es 62 MB. o_o

La prueba no necesita ser tan severa como lo que acabo de explicar. La matematica nos dice que se podrian usar palabras mas cortas para hacer que pases el limite:

La mayoria de los nodos provienen de los finales de las palabras, no de las primeras letras. Vamos a ignorar los nodos para las primeras letras. Si cada letra despues de las primeras 3 crea su propio nodo, entonces basta con encontrar cuantos nodos se necesitan para pasar el limite, y despues cuantas letras se necestan para crear esos nodos.

62 MB = (62 * 2^20) bytes = 65,011,712 bytes = (65,011,712 / 4) punteros = 16,252,928 punteros = (16,252,928 / 27) nodos = 601,960.30 nodos = (601,960.30 / 10^5) letras = 6.02 letras

Si consideramos los otros nodos que ignoramos, eso nos debe hacer exceder el limite con palabras de 9 letras en total, o nos pone bien cerca del limite.

José Carlos
Posts: 13
Joined: 9 years ago
Gender: None specified

Re: 2826 - No Spaces

Post by José Carlos » 6 years ago

De todas formas he enviado varias soluciones aceptadas a este problema y dieron mle. Por lo visto redujeron la memoria original que tenia el problema. Si se le hace rejudge creo que la mayoria de los que lo tenemos aceptado fallariamos.

HaZard
Posts: 114
Joined: 6 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 2826 - No Spaces

Post by HaZard » 6 years ago

No creo que sea que redujeron la memoria del ejercicio, es posible que el antiguo motor de calificación juzgaba mal la memoria, casi siempre ponía 435 bytes de memoria para todo o algo así, Saludos
teruel

HaZard
Posts: 114
Joined: 6 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 2826 - No Spaces

Post by HaZard » 6 years ago

las soluciones con trie dan MLE, lo acepté con un mapa, que no es la solución que más me hubiera gustado
teruel

humbertodiaz
Posts: 97
Joined: 6 years ago
Gender: None specified

Re: 2826 - No Spaces

Post by humbertodiaz » 6 years ago

Yo tambien note eso. Envie mi solucion otra vez y fallo con MLE. No se si fallo por un problema con el juez o si realmente se pasa del limite pero mis calculos anteriores demuestran que no es tan dificil pasarse del limite con un trie. Ah, y no es necesario contar cuantas veces aparece una palabra en la lista. Yo pense que era razonable esperar que las palabras no estarian repetidas, por que entonces eso trae dudas sobre como interpretar repeticiones.

Digamos que nuestra lista de palabras tiene N palabras de L letras. La idea general es que necesitamos una estructura que nos permita combinar multiples busquedas con tiempo O(log N) y espacio O(N log N). Claro que esos limites son para los peores casos - tiempo O(1) seria bienvenido. El trie nos falla por que requiere espacio O(ALN) donde A es el tamaño del alfabeto y nos acercamos bastante a ese peor caso. Otras estructuras que nos podrian servir serian:

1. Trie (mejorado) - Pense en un cambio que se le puede hacer a un trie. Nuestro problema era que los sufijos de palabras distintas pueden crear muchos nodos adicionales. Podemos evitar eso con una regla. Digamos que si llegamos a un nodo sin hijos pero todavia queda un sufijo por insertar en el arbol, podemos guardar lo que queda de la palabra en ese nodo como un string. Asi es claro que quedan letras pero no se crean O(AL) nodos adicionales. Si despues se intenta insertar otra palabra en ese nodo, entonces tambien se crea un nodo para el sufijo que se guardo antes y se continua el proceso recursivamente.

2. Radix tree - Es como un trie mejorado. Las aristas entre los nodos se pueden asociar con partes de palabras en vez de con letras individuales para reducir cuantos nodos hay.

3. Deterministic automaton - Crear un automata minimo que reconozca las palabras que queremos buscar. Es como una version optimizada de un trie para eliminar toda redundancia. Aparentemente existen implementaciones eficientes que permiten construir un automata minimo en O(NL log NL). Sin embargo, yo nunca he usado uno, y me preocuparia que sea dificil de implementar.

La desventaja de las primeras dos opciones es que el proceso de busqueda deja de ser "facil". No es solo descender por un arbol como con un trie. Yo opte por una opcion diferente pero confiable:

4. Hash set - Puedes hacer una estructura improvisada que representa las palabras como un conjunto de hashes. Intentare explicar como funciona mi version - que me permite calcular hashes progresivamente en tiempo O(1) en vez de O(L). Yo tipicamente sacrifico la garantia de que mis resultados siempre seran correctos por reducir tiempo, memoria y complejidad.

Primero, los hashes. Podemos leer las palabras como si fueran numeros en base 27. La razon para escoger 27 en vez de 26 es para que las letras A hasta Z correspondan a los valores 1 hasta 26. Si A corresponde a cero, entonces no se pueden distinguir palabras como AA y AAA por que todas dan cero. Tampoco se pueden distinguir palabras como IRE y AIRE. Las palabras en este ejercicio podrian tener hasta 20 letras. No es posible guardar toda esa informacion en un LL (long long) por que (27^20 - 1) es un valor enorme.

Sin embargo, no es necesario guardar las palabras perfectamente. Un hash solo necesita tener una probabilidad baja de colisiones. Generalmente no hay que garantizar que no hayan colisiones. Podemos calcular los hashes tomando modulo por un divisor grande que sea menos de (2^63 - 1) para poder guardar los valores en un LL. Realmente queremos un divisor mas pequeño para asegurar que no ocurran overflows antes de aplicar modulo. Asi que nuestro divisor deberia ser un numero grande pero menor que ((2^63 - 1) / 27 - 27). Yo escojo numeros primos para mis divisores por mania - no creo que importe mucho aqui.

Una de las razones para usar un trie es por que puedes combinar multiples busquedas, que es importante para la parte de programacion dinamica. Cada letra adicional requiere tiempo O(1) en vez de tener que empezar la busqueda desde cero. Lo mismo aplica para calcular estos hashes. Como interpretamos palabras como numeros, es tan sencillo como "rodar" los digitos del hash anterior multiplicando por 27, y despues se le suma la proxima letra.

Insertar elementos en la tabla y buscarlos es similar. Nuestra tabla puede ser un arreglo de vectores de LL - digamos que es de largo T. Indicamos que una palabra es parte del conjunto con poner su hash dentro de la tabla. Para insertar un hash H, calculamos X = (H mod T) e insertamos H en el vector del indice X. Eso es todo. Para buscar si una palabra esta en el conjunto, calculamos su hash y buscamos si esta en el vector correspondiente. Asumiendo que los hashes se distribuyen casi equitativamente, deben quedar aproximadamente (10^5 / T) hashes en cada vector. Asi que escogemos un valor de T que no deje muchos hashes para verificar, pero que tampoco sea tan grande que inicializar los vectores tome tiempo. Algo como T = 10^4.

Esto me resolvio el ejercicio y he utilizado versiones de esta tecnica en otros ejercicios. Lo mas importante que uno tiene que entender es que esto es un marron - las tablas de hash correctas tambien guardan los datos que corresponden a los hashes dentro de la tabla para verificar si de verdad se encontro un dato. Yo no hago eso para evitar el costo de comparar strings. Si uno escoge el tamaño del hash correctamente (32 bits o 64 bits), entonces la probabilidad de una colision es tan baja que no es necesario verificar para tener resultados correctos en estos ejercicios. Creo que hay hasta demostraciones formales de que esto tiene una probabilidad alta de exito cuando se escoge un divisor primo grande aleatoriamente.

Edit: Ah, se me olvido un detallito. Cuando uno usa un trie, se sabe que uno puede parar de descender por el arbol cuando se acaba la rama. En este caso, no tenemos datos sobre los largos de las palabras o sus sufijos. Yo simplemente guardo el largo de la palabra mas larga. Mi solucion todavia es rapida, aunque tenga que hacer L iteraciones por cada caracter del mensaje.

Post Reply

Return to “Problem set”