Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
54 lines (29 sloc) 11 KB
Voy a intentar dejar algo documentado como hice cada test.
Todo ha sido desarrollado en Eclipse Helios en una maquina W7, excepto el 20 que lo resolví en un VPS personal que tengo en WiredTree, ya que no merecía la pena hacerlo de otra manera.
Por eso de tener vida social realmente solo pude dedicar al concurso de 24 a 3AM de Lunes llegué al test 3, 22 a 3AM del Martes llegue al test 7, 22 a 2AM el jueves sin conseguir pasar el 7, Viernes 23 a 3AM (me salté el 7 y empecé a avanzar rapido), Sabado de 20 a 2AM y el domingo entero hasta las 3AM que pasé el 20. Echando cuentas rapidas salen unas 37 horas, de las cuales 7 u 8 estuve completamente atascado con el 7 y con el 19.
Por comodidad para la ejecución de cada test creé el fichero run.bat que era el que pasaba al submit o test_challenge con un parametro para cada test en concreto, haciendolo bien lo razonable habría sido que solo hubiera habido una clase con main y que instanciase el test concreto con el parametro y lo ejecutara, pero cuando vas con prisas las cosas no se hacen bien :(
Soluciones a los problemas:
1.- Super hard sum: Intenté aplicar lo mismo que en el test, creando un Scanner personalizado para numeros realmente grandes, un parser para los negativos y usando BigInt, java no se lleva muy bien con los numeros realmente grandes, es algo que ya he comprobado en otras ocasiones :(
2.- TLang: Realmente me costó bastante hasta que pillé lo del operador unario de resta, la solución no es 100% valida ya que para una entrada con solo un operador unario de resta falla, pero en general es rapida y comoda.
3.- Emrips: Tests con primos son clasicos en este tipo de competiciones, así que al final uno ya se sabe los trucos, realmente se podía haber reutilizado la lista de emirps entre diferentes inputs y seguramente alguna optimizción mas (la inversion no creo que sea lo más eficiente), pero la solución es rapida y funcional.
4.- Tasks: Primer gran atasco, creo que la solución es de lo más eficiente que se puede hacer, sin ningun tipo de recursividad pero está realmente optimizada para el fichero de entrada del test en el que la mayoría de las dependencias eran de atras hacia adelante, así que lo mejor era invertir la forma de recorrer el fichero una vez leidos los tiempos de las tareas, solo había una tarea que dependia de una anterior que se podía resolver en una segunda pasada (por si acaso lo dejé para que pudieran quedar n niveles de dependencias después de la pasada inicial), creo recordar que tardaba unos 6-10 segundos en procesar el fichero y luego las respuestas eran o(1).
5.- Milkman - Cows: Aquí empezamos con los problemas en los enunciados y ejemplos escritos, en cualquier caso opté por hacer algun objeto por eso del que dirán y hacer una solucion puramente recursiva, seguramente con DP se podría haber hecho mejor y mas eficiente, pero iba con prisas y funcionó a la primera así que no le dí más vueltas.
6.- Clock: Después de muchas cuentas en papeles y ajustes varios me quedé atascado un buen rato por pensar que el 9 tenía mas segementos de los que tenía, no habría estado de mas un dibujo con todos los numeros por que sobre todo 6 y 9 se pueden representar de varias formas. Solución O(1) aunque pasé de hacer los calculos por encima de 10 horas, se que no debía pero al menos está documentado.
7.- Tiles: Por desgracia aquí me quedé atascado durante horas y tuve que saltarlo, lo triste es que ya conocía http://en.wikipedia.org/wiki/Levenshtein_distance pero en su momento busqué un poco y no la encontré, así que empecé a reinvenar la rueda de mil formas distintas, llegando a sacar el 50% de los casos de prueba con una solución altamente ineficiente (que queda para la posteridad aquí subida). Ahora a toro pasado la solución no me ha costado más de 1 hora pese a que el validador de soluciones post concurso está estropeado y me he comido la cabeza hasta ver que ese era el problema.
8.- Biologist: Seguro que tirando por: http://en.wikipedia.org/wiki/Sequence_alignment se pueden encontrar algoritmos rapidos y buenos, pero a falta de buenos algoritmos conocidos tirando de inventiba saque uno no demasiado pesado (no creo que la ejecución media esté por encima de O(m*n) ) con algunas optimizaciones para acelerarlo, creo que tarde 15 min y se notó el cambio de mano a la hora de hacer los tests.
9.- Christmas: Otro test realmente sencillo (más que que todos los 2-7) solo tenía la problematica del tamaño de los tiempos, tirando de BigInt salió en nada.
10.- Key Combos - HotKeys: Intenté hacer una solución con complejidad minima, aunque quedó bastante enrevesado, al almacenar que combos activan cada tecla la solucion es realmente rapida, pero es cierto que no era completa ya que en caso de que se activen varias o ninguna (casos no especificados en el enunciado) mi solución solo genera basura.
11.- Gas: Solución recursiva bastante obvia, el problema aqui es que sin usar DP al enviar el test se quedaba "colgado" fue cuando empecé a usar Log4j para sacar info de los datos de entrada y debug sin estropear la salida, realmeent el problema era que uno de los casos del submit era con 64 gasolineras dando 2^64 caminos alternativos y eso se tarda mucho en evaluar, con DP realmente evaluas muchas menos soluciones (probablemente 128 o algo así) y el resto las reutilizas, obviamente eso se nota mucho en tiempo de ejecución a costa de un consumo de memoria mínimo.
12.- Stargate: Otro de los atascos serios de mucha gente, esté lo tenía más fresco ya que revisando cosas de DP llegué al algoritmo de Dijkstra ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ) que modifiqué para soportar los pesos negativos, los bucles y alguna cosa más, por desgracia en su momento no llegué a descubir el algoritmo de Bellman - Ford (http://en.wikipedia.org/wiki/Bellman-Ford_algorithm) que hace lo mismo pero bien hecho, creo que el mio es practicamente identico al Bellman - Ford, pero no estoy seguro de ello. Tuve algun problema con el descubrimiento de bucles reductores del espacio tiempo fuera del camino más corto, pero al final llegué a una solución valida y eficiente.
13.- Clock2: Más de lo mismo, adapté el primer Clock sin mucho problema, aunque volví a dejar tirado la solucón para tiempos de más de 10 horas.
14.- Colors: Aquí ya empecé con las novedades, jamás había tocado imagenes en Java, así que me tocó investigar bastante, como funcionaba el modelo ARGB las buffered images y demás, el test era bastante simple, pero la manipulación de imagenes puede ser bastante complicada segun el lenguaje en el que lo programes y las librerias que uses.
15.- Robot - Alfonso: Intenté pensar en algun algoritmo optimo para esto, manejando los rectangulos, buscando conflictos, conflictos de conflictos y al final pensé "¿Para qué? si esto ya lo hacen los algoritmos de coloreado" me creé mi imagen, fuí pintando y conté después los colores, solución un poco triste pero funcional 100%, obviamente se puede hacer lo mismo con una matriz, pero supusé que el awt.Graphics2D estaría mejor optimizado, así que no pensé mucho.
16.- Bus: Esto cantaba a algoritmo existente, así que busqué un poco y casi que copy&pastee http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm al ver que era una optmización de http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm , funcionó a la primera y a por el siguiente.
17.- Empieza la diversión, fué fácil descubrir la codificación base64, sacar la imagen por las cabeceras, ver el texto oculto y volverme loco intentando sacar más info, busqué metadatos PNG, crucé la imagen con la del 14, herramientas de steganografía libres, pero no se me ocurrió que estuviera hecho a manubrio, por twitter empezó a circular lo del LSB y demás y me centré en un area de la imagen concreto (que no era el bueno) luego ya opté por ir probando todo, todos los ordenes de colores, despreciar el 9º bit, el 1º o encadenarlo, desncriptar toda la imagen o linea a linea hasta que dí con la buena, realmente creo que este problema se les fué de las manos, preferiría que hubiera tenido 5 subniveles con pistas aunque fueran muy sutiles a simplemente probar todo, al final hay que hacerlo a mano y no demuestras nada. Todas las pruebas y codigo estan hechas en la clase prueba.
18.- Riddle: Esté era un poco más simple aunque me atasqué bastante al final tambíen, pensé que lo del las franjas rojas sobre verdes y sus distancias aportaría algo para el orden ya que desde un princpio quedó claro que era un texto en inglés desordenado (yo solo estaba usando el azul para sacar letras) y me costó bastante hasta que probé a usar todos los colores, pero dí con ello.
19.- Cesar: Era ya el Domingo por la tarde y yo solo quería llegar con todos al 19, por las pistas y con lo que leí me pareció todo tan obvio que casi saque la solución en minutos, estaba claro por las pistas que era un DES, el NOT fue solo mirar los bits con la calculadora de windows y resultó obvio, el XOR no estaba oculto y el código Cesar es un clasico para el que sepa un poco de criptografía. Por desgracia todo parecía que era bastante razonable pero el resultado aunque casi legible no era nada lógico, entedí que el DES estaba bien hecho por que hasta el padding cuadraba y el NOT no daba lugar a dudas, no supues nada raro en el XOR así que me puse a probar si el descifrado del Cesar estaba mal hecho sin mucha suerte hasta que soltaron la pista de que el XOR no era normal, con lo del WoW estuve buscando un poco y llegué a: http://forum.x86labs.org/index.php?topic=6406.0 decidí probar esa implementación y Bingo! el descrifado del Cesar no era perfecto, pero suficiente para entenderse, no sé si se puede hacer mejor pero valía para lo que necesitaba así que hice un par de pruebas y lo deje.
20.- Clumsy: Lo leí, lo releí y estaba perplejo, ni idea de como solventar el problema, ni conocimientos de OpenSSL, RSA ni nada, sabía que estaba entre los primeros y era la 1:30AM del Lunes, tenía que currar a las 9AM así que me puse como un loco a googlear, asumí que el decirnos que era una debian de 32 bits era para algo, después de buscar bastante dí con el fallo del PRNG pero aun sin idea de como explotarlo, avanzando por ahi dí con http://digitaloffense.net/tools/debian-openssl/ que tanto google como mi antivirus detectaban como maldad, así qué opté por abrirlo y me quedó claro como iba el tema.
Como gracias a $deity tengo un VPS para mis cosas, me conecté me bajé las claves he hice unas pocas pruebas hasta dar con lo que quería, en una primera pasada pensé que el script dejaría el texto desencriptado en el fichero sin más pero descubrí después de dejarlo correr varios minutos que si fallaba se cargaba el fichero, así que buscando un poco más opté por parar cuando el fichero acabará con datos et voila! test 20 resuelto, eran las 2:52AM y yo sin cenar ni salir de casa en todo el día.
Lo twittee, fuí a cenar y cuando volví comprobé con los stats que estaba entre el top 3, respondí unos pocos twitts y a dormir.
El shell está el solito en la carpeta 20 ya que no encajaba mucho con el resto.
Esto, esto, esto... esto es todo amigos!!!!!
You can’t perform that action at this time.