Discusión de soluciones de la octava competencia por equipos

Como de costumbre, el jueves en la mañana se realizó la discusión de las soluciones de la competencia anterior. En esta ocasión el debate fue mayor, ya que los equipos plantearon diversas variantes de solución a los problemas, y se discutieron alternativas para optimizar las soluciones existentes: prueba de que los concursantes están aprovechando su tiempo fuera de las competencias y están haciendo un fructífero estudio individual.

Ray hace algunas precisiones sobre el
test de Miller-Rabin.

El ejercicio Prime or Not (Categoría: Matemática) fue explicado por Mario Ivan Cid, del equipo UCi-06. La solución que dio el equipo fue aplicar el test de Miller-Rabin para determinar si los números son primos. Luego el entrenador Ray hizo algunas precisiones, como por ejemplo, advirtió que el test no es efectivo para los números de Carmichael, aunque al parecer entre los juegos de datos del ejercicio no había ninguno de estos números. Aclaró que este test es eficiente para números de hasta 20 bits, y que para números mayores de 20 bits es mejor utilizar el test de Lucas-Lehmer. Terminó diciendo que para mayor claridad, se puede consultar el código fuente de las librerías de Java, ya que la implementación del método isProbablePrime de la clase BigInteger contiene ambos tests.

José Carlos explica el ejercicio Greedy Island.

El ejercicio Greedy Island (Categoría: Flujo de costo mínimo / Matching) fue explicado por José Carlos del UCi-03. El concursante explicó que para resolver el ejercicio se puede utilizar el cálculo de flujo máximo, costo mínimo sobre un grafo, o la asignación húngara.

El ejercicio Queens, Knights and Pawns (Categoría: Ad-Hoc) fue explicado por Adrián Hondal, del UCi-04.

El ejercicio Pie (Categoría: Búsqueda binaria) fue explicado por Jorge Fuentes, del UCi-05. El equipo aplicó una búsqueda binaria sobre el volumen del pastel, y si era posible repartirlo, aumentaba la cantidad y seguía buscando, si no, se disminuía la cantidad.

Castrillón explica la dinámica del algoritmo LCS
y cómo su solución se basa en ella.

Alkaid explica cómo optimizar
la solución propuesta.

El ejercicio DNA Sequences (Categoría: Programación dinámica) fue explicado por José Luis Castrillón, del UCi-01, quien hizo gala de su caligrafía mientras explicaba cómo a partir de una variante del algoritmo LCS se puede llegar a la solución de este problema. Dijo también que los juegos de datos del mismo no deben contener el peor caso (secuencias largas de caracteres repetidos), ya que en ese caso el ejercicio debería haberse pasado del límite de tiempo. El concursante Alkaid Cruz Llanes, del UCi-06, comentó que su equipo no había aplicado esta variante de solución precisamente porque pensaron que no cumpliría con el requisito del tiempo, además que explicó una forma de optimizar la solución propuesta por Castrillón.

El ejercicio Travelling Shoemaker Problem (Categoría: Teoría de Grafos) fue explicado por el entrenador Ray. Explicó que este problema se puede resolver tomando a las ciudades como aristas que conectan a las confederaciones, entonces queda verificar si en el grafo existe un camino de Euler.

Carlos Julio explica su intento de solución.

El ejercicio Cuckoo Hashing (categoría: Ad-Hoc) fue explicado por el entrenador Ray, quien comentó que la vía de solución es acomodar las palabras, y comprobar si existe algún ciclo. Carlos Julio Figueiras, del UCi-03, comentó que intentaron resolverlo aplicando flujo sobre un grafo, pero por esa vía no lograron hallar la respuesta correcta al problema.

El ejercicio Soccer Bets (Categoría: Ad-Hoc) fue explicado por Randy Mujica, del equipo UCi-02. El equipo simplemente contó la cantidad de veces que ganaba cada equipo, y al final el equipo con la mayor cantidad de victorias era el ganador del torneo. Otros equipos comentaron que también es posible buscar el equipo que nunca perdió, ya que como la modalidad de juegos es eliminatoria, el equipo campeón no puede haber perdido en ninguna etapa.

Nelson explica las fórmulas del tetraedro.

El ejercicio Point in tetrahedron (Categoría: Geometría computacional) fue explicado por Nelson Peñate, del UCi-01, quien explicó varias fórmulas necesarias para dar solución a este problema.