Charla de matemática

Este martes en la tarde, el entrenador Yaniel Calviño brindó una charla acerca de fórmulas matemáticas comunmente utilizadas en las competencias de programación. La charla giró fundamentalmente acerca de temas de geometría computacional, comenzando por las relaciones entre los triángulos y las circunferencias inscritas y circunscritas a ellos. Luego se habló de otras fórmulas y propiedades presentes en los triángulos, así como de las rectas fundamentales que se trazan en ellos.

La segunda parte de la charla la brindó el concursante Mario Iván Cid, quien explicó cómo utilizar la clase complex de la librería estándar de C++ para representar puntos en el plano, como pares de coordenadas (x;y), y cómo se pueden utilizar varios de los métodos y fórmulas de los números complejos para hacer cálculos relacionados con puntos y rectas en el plano.

Discusión de soluciones de la novena competencia por equipos

Hoy martes 6 en la mañana se realizó la discusión de las soluciones a los problemas de la novena competencia por equipos.

El ejercicio The Proper Key (Categoría: Ad-Hoc) fue explicado por el entrenador Ray Williams.

Entre todos se debate la solución al
ejercicio Fill the Cisterns.

El ejercicio Fill the Cisterns (Categoría: Búsqueda binaria) fue explicado entre todos los concursantes, quienes expusieron distintas variantes para resolverlo, lo cual generó un extenso debate.

El ejercicio Solitaire (Categoría: Recorrido de grafos) fue explicado por el entrenador Ray Williams, quien explicó cómo para este ejercicio era mejor hacer dos búsquedas a lo ancho que partieran de los extremos y se encontraran en el medio con 4 niveles de profundidad cada una, que hacer una sola búsqueda a lo ancho con 8 niveles de profundidad.

Alkaid Cruz Llanes, del UCi-01

El ejercicio Distinct Subsequences (Categoría: Programación dinámica) fue explicado por Alkaid, del nuevo equipo UCi-01, quien explicó cómo estructurar la programación dinámica y qué significado dar a las filas y columnas de la tabla para resolver este problema.

El ejercicio Distinct Increasing Subsequences (Categoría: Programación dinámica) fue explicado también por Alkaid, quien explicó las similitudes y diferencias de este ejercicio con el anterior. A continuación, luego de explicar la dinámica, enumeró ciertas optimizaciones que es necesario hacer para poder cumplir con el límite de tiempo de este ejercicio (como el uso del árbol binario indexado), así como el proceso de normalización que es necesario aplicar a los resultados. Concluyó que este ejercicio es una mezcla de programación dinámica con estructuras de datos.

En este momento se recibió la visita del rector al Campamento.

Eddy explica cómo utilizó
la búsqueda binaria

Calviño explica las construcciones
auxiliares necesarias

El ejercicio Area of a Garden (Categoría: Geometría computacional) fue explicado por Eddy, del nuevo UCi-02, quien sorprendió a concursantes y entrenadores cuando explicó la solución que le dio al ejercicio utilizando una búsqueda binaria. Cuando concluyó y se debatió la solución, el entrenador Yaniel Calviño explicó la solución tradicional a este ejercicio mediante la geometría computacional, para lo cual se auxilió como es típico en este tipo de ejercicios en una construcción auxiliar. Al finalizar, Nelson Peñate explicó una vieja fórmula que conocía, que es posible utilizar en este caso.

El ejercicio Adjacent Bit Counts (Categoría: Programación dinámica) fue explicado nuevamente por Alkaid, del UCi-01. Alkaid explicó cómo estructurar la dinámica para resolver este ejercicio y al final acotó que es posible precalcular todas las soluciones al principio del programa y luego simplemente responder cada entrada con los valores precalculados.

José Carlos González, del UCi-02

El ejercicio Frequent Prime Ranges (Categoría: Programación dinámica) fue explicado por José Carlos, del nuevo equipo UCi-02. José Carlos explicó cómo estructurar la dinámica para resolver este ejercicio.

Mario Iván Cid, del UCi-01

El ejercicio Clock Hands (Categoría: Ad-Hoc) fue explicado por Mario, del UCi-01. Mario explicó las fórmulas matemáticas que elaboró para resolver este ejercicio, y acotó que hay que validar el caso que entre las 11 y las 12 nunca se cruzan las manecillas, lo cual le costó algunos envíos incorrectos al problema.

Visita del rector de la UCi al campamento de entrenamiento

En horas de la mañana de hoy martes, mientras los equipos y los entrenadores realizaban la habitual discusión de los ejercicios de la competencia anterior, se recibió en el campamento la visita del rector de la universidad, Dr. Antonio Romillo Tarke, y de la vicerrectora de formación, MsC. Idelsi Martínez Ungo.

Romillo recibió una detallada explicación del cronograma del campamento y las actividades que se han realizado hasta el momento por parte de Dovier, así como de la estrategia que se ha seguido en el entrenamiento y los ajustes en los equipos. Luego, se dirigió a los concursantes, y les explicó que el campamento tiene dos aristas: la primera es elevar los resultados en las competencias, la segunda es experimentar para hallar un método de formación para los estudiantes de alto rendimiento. Al final, realizó un intercambio con los concursantes y entrenadores, el cual concluyó con las palabras ¡éxitos y adelante!

Dovier explica las actividades realizadas en el campamento al rector.

Resultados de la novena competencia por equipos

TCW5C1
Problemas
Ranking

Hoy lunes 5 de septiembre, mientras la Universidad (y el resto del país) comenzaba su curso escolar, se efectuó la novena competencia por equipos del Campamento. Especial importancia reviste esta competencia, ya que es la primera que se hace luego del reajuste de los equipos.

Los ejercicios seleccionados fueron:

• The Proper Key (Categoría: Ad-Hoc)
• Fill the Cisterns (Categoría: Búsqueda binaria)
• Solitaire (Categoría: Recorrido de grafos)
• Distinct Subsequences (Categoría: Programación dinámica)
• Distinct Increasing Subsequences (Categoría: Programación dinámica)
• Area of a Garden (Categoría: Geometría computacional)
• Adjacent Bit Counts (Categoría: Programación dinámica)
• Frequent Prime Ranges (Categoría: Programación dinámica)
• Clock Hands (Categoría: Ad-Hoc)

El nuevo equipo UCi-02, armado con miembros de los antiguos UCi-01 y UCi-03, combinó la rapidez del último con la potencia del primero y abrió el ranking a los 35 minutos con la solución al problema Fill the Cisterns. Inmediatamente le sucedió el nuevo UCi-01 (antiguo UCi-06), quien se decidió a no quedarse atrás cuando resolvió el problema Adjacent Bit Counts. Estos dos equipos se mantuvieron aceptando ejercicios y fueron los únicos integrantes del ranking hasta cerca del fin de la tercera hora de competencia, cuando el UCi-04 saltó con agresividad y resolvió los problemas Clock Hands y Fill the Cisterns, con sólo 4 minutos de diferencia. Como hecho curioso, los dos equipos que quedaron en el primer lugar de la competencia (cada uno con 3 problemas resueltos), no coincidieron en ninguno de los problemas resueltos: el UCi-01 resolvió Distinct Subsequences, Adjacent Bit Counts y Clock Hands mientras que el UCi-02 resolvió Fill the Cisterns, Area of a Garden y Frequent Prime Ranges. El último en unirse al ranking fue el nuevo UCi-03, que a los 200 minutos aceptó Fill the Cisterns.

Fill the Cisterns y Clock Hands fueron los problemas con mayor cantidad de aceptados, ya que fueron resueltos por 3 equipos. Quedaron sin resolver los problemas The Proper Key, Solitaire y Distinct Increasing Subsequences.

Los resultados de la competencia fueron los siguientes:

Rank	Equipo	ACs	Tiempo
1	UCi-01	3	361
2	UCi-02	3	371
3	UCi-04	2	402
4	UCi-03	2	579
5	UCi-05	0	0
6	UCi-06	0	0

Resultados de la cuarta competencia individual

TCW4C3
Problemas
Ranking

Hoy viernes 2 de septiembre se efectuó la cuarta competencia individual del Campamento. En esta ocasión ningún concursante se quedó sin aceptados, si bien es cierto que todos los concursantes (excepto el ganador) aceptaron sólo un ejercicio. El ranking a partir del segundo lugar se decidió únicamente por el tiempo empleado.

Los ejercicios seleccionados fueron:

• Build the Fence (Categoría: Geometría computacional)
• Permutation generator (Categoría: Matemática, cálculo de combinatoria)
• He is offside! (Categoría: Ad-Hoc)
• Integral Maximization (Categoría: Algoritmos ávidos / Matemática)
• Longest Common Difference Subsequence (Categoría: Programación dinámica)

El ranking abrió a los 5 minutos, cuando Eddy Morales del UCi-01 aceptó el ejercicio que luego sería resuelto por todos los concursantes: He is offside! Le siguió Alkaid Cruz, del UCi-06, a los 8 minutos con el mismo ejercicio. Y uno por uno los demás concursantes fueron resolviendo el mismo ejercicio, hasta el minuto 33 cuando Jorge Luis Acosta del UCi-02, fue el último en unirse al ranking. El ranking se mantuvo sin variaciones hasta casi el final de la competencia, cuando faltando 13 minutos Mario Iván logró resolver el ejercicio Integral Maximization y se convirtió así en el único concursante en tener dos aceptados.

El ejercicio más resuelto fue He is offside!, el cual fue aceptado por los 18 concursantes. El único otro ejercicio que fue resuelto en toda la competencia fue Integral Maximization, sólo resuelto por Mario. A lo largo de la competencia los concursantes se mantuvieron intentando resolver los otros ejercicios, pero el jurado rechazó todas las soluciones tentativas.

Los resultados de la competencia fueron los siguientes:

Rank	Concursante	Equipo	ACs	Tiempo
1	Mario Iván Cid Vázquez	UCi-06	2	180
2	Eddy Roberto Morales Pérez	UCi-01	1	5
3	Alkaid Cruz Llanes Hernández	UCi-06	1	8
4	Jorge Fuentes Rodríguez	UCi-05	1	9
5	Leandro González Vallejo	UCi-06	1	11
6	Luis Andrés Valido Fajardo	UCi-05	1	12
7	Ernesto Martínez Riverón	UCi-03	1	12
8	Nelson González Peñate	UCi-01	1	13
9	Luis Daniel Sierra Corredera	UCi-04	1	19
10	Carlos Julio Figueiras Carrera	UCi-03	1	20
11	Adrián Hondal Hernández	UCi-04	1	20
12	Jose Luis Castrillón Garrido	UCi-01	1	22
13	José Lozano Hernández	UCi-02	1	25
14	Jorge Roberto Jova Rodríguez	UCi-05	1	26
15	José Carlos González Fernández	UCi-03	1	28
16	Jorge Luis Acosta Alonso	UCi-02	1	33
17	Randy Mujica Díaz	UCi-02	1	45
18	Amado Lázaro Solá Santana	UCi-04	1	49

Charla sobre flujo máximo con costo mínimo

Este jueves el entrenador Vladimir Antonio Charchabal impartió una charla sobre el tema flujo máximo con costo mínimo en un grafo. El entrenador comenzó recordando el algoritmo de flujo máximo como introducción, y a continuación pasó a enunciar el problema de flujo máximo con costo mínimo. Describió la modificación necesaria al algoritmo, y explicó cómo utilizarlo para resolver el problema de la asignación de trabajadores a tareas. Explicó que si lo que se desea es maximizar en lugar de minimizar, lo que se hace es poner los costos negativos en el grafo y ejecutar el mismo algoritmo.

Luego, a manera de ejemplo, indicó cómo utilizar el algoritmo para resolver el problema A Knights’ Tale. Luego se discutió entre los concursantes que una alternativa para resolver el problema es la asignación húngara, algoritmo que es más rápido pero que tiene limitantes y no se puede utilizar en todos los casos que el algoritmo de flujo máximo con costo mínimo, que es más general. Para finalizar, se explicó también cómo utilizar el algoritmo para resolver el problema Greedy island.

El entrenador escucha mientras los concursantes plantean dudas y sugerencias.

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.