Code-ate! Primer Concurso de Programación de 106

[Bill]

Pues nada. Ydrojen, vencedor por abandono de todos los demás. 

[Ydrojen]

Ey, ya que solo se ha presentado uno haz un análisis chulo, di cuantos test he superado y esas cosas

[Bill]

Nah, ando decepcionado. No contigo, con el resto. Pensaba que la chispa de talento del foro sería algo más grande, pero vamos, error mío... no hay más que ver cómo se os dan las matemáticas para algoritmica, como los juegos que puse en la sección de juegos de lógica  El talento se demuestra enfrentándose a retos. Es como los juegos de rol, si no te enfrentas al bicho enorme y pasas dificultades, porque además quieres hacerlo, no consigues experiencia y no mejoras.

Este problema era de nivel bajo. Tú fuiste el primero en enviar respuesta, tu tiempo de respuesta fue muy bueno. En cuanto a performance también eres el ganador, pero porque eras el único participante. De los unit tests pasaste 9 de 10, uno está fallido porque era el del enter extra al final del input.

El input para probar la performance es:

Sorry but you are not allowed to view spoiler contents.

Tu forma de resolver es correcta y rápida de programar, pero su performance sufre un poco porque no eliminas posibilidades. Construyes el TreeMap para representar al grafo, y haces el backtracking, pero olvidas que algunas aristas no tienen por qué existir.

Al grano, vamos a ver cómo sería una solución construyendo el grafo, algo más óptima, con un ejemplo:



Es a partir de ahora dónde viene lo divertido:


Te he puesto dos aristas en rayado. Una es C->e, que no llega a insertarse al grafo, porque ya hay un camino más largo para llegar de "C" a "e". La otra es o->s, que se elimina, porque al añadir o->e->s ya existe un camino más largo para llegar. Esto es lo que no tiene tu solución, la eliminación de esos caminos.

Pongo ya todos los pasos hasta el grafo final:









A partir de aquí es recorrer el grafo para dar las soluciones, que creo que está claro. Se clona el grafo, y se escoge cada nodo para cada disyuntiva, para recorrer todas las posibilidades, bien sea dentro de una recursiva o usando una pila para soluciones.

[Ydrojen]

Bueno, yo no llego a "montar" el grafo, con la información que almaceno se puede montar pero no monto la estructura como tal.

Primero recorro el input almacenando para cada letra las letras que se que van delante. Luego para montar la solución miro en ese momento las posibles candidatas, que son las que no tengan ninguna delante, clono el mapa para cada candidato eliminando esa letra del mapa y de la lista de anteriores de las demás y vuelvo a mirar las que no tienen ninguna delante.

Lo único que podría mejorarse es que cuando cojo X candidato tengo que recorrerme las listas de anteriores de los demás para eliminar X si lo tiene. Si cuando recorro el input me fijo en no guardar las aristas esas que tu quitas, a la hora de recorrer la lista para eliminar X tendrían menos elementos cada lista y lo haría más rápido, aunque tienes mas operaciones al recorrer el input así que al final tampoco es tanta mejora...