Soluciones a Liga Omegaup – Fase 1

Para este problema, consideramos un arreglo de ocurrencias O sobre los elementos del arreglo. De modo que la respuesta está dada por

\sum\limits_{i=A}^B O_{i}

Si consideramos el mismo arreglo de ocurrencias O sobre los elementos del arreglo, la respuesta está dada por O_k.

Podemos generar todos los elementos de la secuencia de Fibonacci hasta 30000, y guardarlos en un mapa M, de modo que M_k = 1 si k es un elemento de Fibonnaci, y M_k = 0 en caso contrario. Generamos la respuesta simplemente iterando desde i = 4 hasta i = N - 1, e imprimimos i si M_i = 0.

La clave para este problema, es usar variables que no provoquen un desbordamiento, por ejemplo, unsigned long long. Luego, es conocido que la serie de Fibonacci crece rápidamente, lo suficiente, como para generar la secuencia con todos sus elementos menores o iguales a N, guardando por cada uno su respectiva posición en ella. Por lo tanto, basta con checar si N es un elemento, e imprimir su posición. En caso de no serlo, imprimimos -1.

Este tipo de problema es conocido como straight-forward. Podemos guardar las estaciones de radio, y checar cuál estación es la mas cercana a la frecuencia dada, con una simple resta. En caso de haber dos estaciones con la misma distancia, la respuesta es la mayor. Solo debemos cuidar que la frecuencia esté dentro del rango permitido.

En este problema lo que tenemos es un grafo dirigido acíclico con aristas pesadas (intuitivamente, es un árbol, sin la propiedad de que cualquier par de nodos estan conectados por un único camino).
Los vértices son los eventos temporales, las aristas son dirigidas de p_i a i, y su peso es d_i. Además, cada vértice contiene un valor extra r_i. Un grafo que podemos asociar al primer caso de ejemplo es el siguiente.

Sean v_1 y v_k dos vértices distintos, tales que v_1 es ancestro de v_k. Es decir, existe un camino v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k en el grafo. Definimos S(v_1, v_k) como

\sum\limits_{i=1}^{k - 1} d_{v_i}

 

Es decir, la suma de los pesos en las aristas del camino.
De modo que el problema se convierte en: Para cada vertice v, contar cuántos vértices u en su “subárbol” \; existen tales que

r_u - S(v, u) \geq 0

Porque esto siginifica que tenemos suficientes segundos para viajar por el tiempo desde u hasta v.

Consideremos un arreglo E, donde la entrada E_v guarda cuántos descendientes u de v satisfacen

r_u - S(v, u) \geq 0

Pero

r_u - S(p_v, u) < 0

Donde p_v es el padre de v. Si v = 0, entonces no hace falta considerar a su padre, puesto que no podemos viajar por el tiempo a algún ancestro de 0 (ya que ni siquiera existe alguno).

En otras palabras, E_v guarda cuántos descendientes de v llegan a lo mas al vértice v.

También consideremos un arreglo D, donde la entrada D_v guarda cuántos descendientes u de v satisfacen

r_u - S(v, u) < 0

Es decir, D_v guarda cuántos descendientes de v no pueden llegar al vertice v.

Y además mantengamos un arreglo T, donde la entrada T_v guarda el tamaño del “subárbol” de v (incluyendo a v). En otras palabras, cuántos descendientes tiene v en total mas el mismo.

Por lo tanto, la respuesta final para el vértice v está dada por

(T_v - 1) - \sum\limits_{v \rightarrow u} (E_u + D_u)

donde u es un hijo directo de v.
Ya que esto calcula cuántos descendientes de v si pueden llegar a v.

Para el cálculo de nuestros arreglos, hacemos una dfs sobre el “árbol”  (partiendo del vertice 0). Para cada vértice u, hacemos una búsqueda binaria sobre un arreglo que mantenga la suma acumulada de los costos sobre las aristas que forman parte del camino de 0 a u, que nos devuelva el máximo ancestro v al que podemos llegar desde u.  Lo que nos dice que  E_v actualiza su valor a E_v + 1 (inicialmente, E_1 = E_2  = \ldots = E_n = 0). Esto se puede hacer usando un arreglo global. La idea es añadir la suma acumulada, luego explorar recursivamente el subárbol de u, y luego quitar la suma acumulada que añadimos. Esto es particularmente sencillo si usamos un vector de la STL para el arreglo global.

El arreglo T se calcula facilmente en la misma dfs, ya que

T_v = 1 + \sum\limits_{v \rightarrow u} (T_u)

Ahora podemos generar D, al estilo de programacion dinámica usando E. Notemos que

D_v = \sum\limits_{v \rightarrow u} (E_ u + D_u)

Lo que se puede hacer en la misma DFS.

Por lo tanto, nuestro algoritmo tiene complejidad O(Nlog(N)).

Primero reescribamos la expresión dada como

k = \dfrac{xy}{x + y}

De donde podemos despejar y como

y = \dfrac{xk}{x - k}

Sin perdida de generalidad, supongamos x \leq y, entonces se tiene

x \leq \dfrac{xk}{x - k}

x^2 \leq 2xk

x \leq 2k

Por lo tanto, podemos iterar x desde 1 hasta 2k, obtenemos y, y verificamos que k = \dfrac{xy}{x + y}, y > 0.

Guardamos las parejas que satisfazcan dichas condiciones y las imprimimos en el orden requerido, cuidando no repetir alguna respuesta.

Lo que nos deja con un algoritmo de complejidad O(k).

Una solución alternativa es la siguiente:

Te puedes dar cuenta que x, y > k, entonces el problema se convierte a  buscar a y b que cumplan

\dfrac{1}{k} = \dfrac{1}{k + a} + \dfrac{1}{k + b}

con a,b > 0. Si simplificas la igualdad llegas a que k^2 = ab, así que todo se reduce a encontrar las parejas de divisores a, b de k^2.  Lo que deja también un algoritmo de complejidad O(k).

Nota: Agradezco a José Tapia y a Carlos Galeana por su colaboración en el problema G.

Se realiza la 1era Competencia Peruana de Informática Online en omegaUp

1ra Competencia Peruana de Informática Online
1ra Competencia Peruana de Informática Online

El pasado domingo 28 de mayo de 2017 se realizó la 1era Competencia Peruana de Informática Online (CPIO). Organizada por la Federación Olímpica Peruana de Informática (FOPI), la CPIO es la primera competencia en su tipo que convoca a alumnos pre-universitarios de todo el Perú para conformar la delegación peruana rumbo a la Competencia Iberoamericana de Informática y Computación (CIIC) 2017.

Fundada en diciembre de 2016 por Aldo Culquicondor, Edson Ticona, Jonathan Quispe, L. Rodolfo Nájera, Raúl Gallegos, Rodolfo Mercado y Yesica Aquino, la FOPI busca fomentar la informática competitiva pre-universitaria, apoyando a los niños y jóvenes peruanos a desarrollarse en este ámbito, preparando una delegación que represente al Perú y consolide logros internacionales.

La CPIO es una competencia multi-nivel de programación para jóvenes peruanos, con habilidades de resolución de problemas mediante el análisis, la lógica, el ingenio y la implementación de soluciones en un computador. El concurso realizado en omegaUp contó con la participación de competidores de las principales ciudades peruanas: Arequipa, Callao, Chepen, Cusco, Ica, Lima, Piura, Pucallpa, Puno y Tacna.

Al ser la primera competencia de programación competitiva en el Perú, se espera que CPIO marque el inicio del desarrollo de la informática en los jóvenes peruanos y como consecuencia un mejor desarrollo tecnológico en aquel país sudamericano, mencionó Aldo P. Culquicondor Ruiz, presidente de la FOPI.

Luego de la competencia, quedaron seleccionados ocho competidores para representar al Perú en la CIIC el próximo 10 de junio: Joaquin Rodrigo Palma Ugarte y Stheven Julmar Quispe Llamocca de Arequipa, Anthony Dante Yataco Torres y Nicolas Ticona Valdivia de Lima, Carlos Daniel Ramos Arellano de Piura, Johan Frank Cachicatari Ticona y Marcela Veronica Apaza Vilca de Puno y Roberto Carlos Huamán Rivera de Tacna.

Con la realización de esta competencia, la organización sin fines de lucro omegaUp da un paso importante para cumplir su objetivo de aumentar el número de ingenieros de software talentosos en todos los confines de América Latina.

El camino de México rumbo a la IOI 2015

Un año más ha pasado y México ya tiene lista su delegación que nos representará en la International Olympiad in Informatics 2015 a celebrarse en Kazakhstan, del 26 de Julio al 2 de Agosto. A continuación presentamos la colección de exámenes y problemas que se usaron durante el preselectivo dentro de omegaUp. Esperamos que esta colección de problemas sirva de entrenamiento a futuras delegaciones de México y otros países de América Latina.

Selección 2015 México De izquierda a derecha, los integrantes de la Selección Mexicana de Informática 2015 son:

  1. MEX-4: Emmanuel Antonio Cuevas (Emmanuel_Antonio)
  2. MEX-2: Carlos Galeana Hernández (charlyhlms)
  3. MEX-1: Juan Carlos Sigler Priego (Juan_Carlos_Sigler_Priego)
  4. MEX-3: Ángel David Ortega Ramírez (blak_dragon1)

Continue reading “El camino de México rumbo a la IOI 2015”

Trucos para ser más cool

Después de un rato de investigación y experimentación, por fin me tomo el tiempo para escribir este post y presentarles algunos trucos que, considero, podrían ayudarles a simplificarse la vida cuando programen y, obviamente, a ser mucho más cool.

¿Cansado de importar librerías como asíatico en TopCoder? ¡Aquí está la solución!

Muchas veces es nefasto encontrar varios (sino es que miles) errores al compilar a causa de librerías que hemos olvidado incluir. Existe una librería que, al incluirla, agrega todas las librerías estándar de C++ a nuestro código, ¡incluso las de la STL!

¿Que clase de brujería es esta? Seguramente se estarán preguntando. Muy sencillo, solo necesitan escribir la siguiente línea de codigo: #include <bits/stdc++.h>

(Actualización) Gracias a el comentario de lhchavez por remarcar el hecho de que esta línea funciona únicamente con el compilador gcc. Pese a esto, gran parte de los evaluadores actualmente usan gcc, por lo que podemos confiar en su uso, al menos en omegaUp. En caso de que la librería anterior no siga siendo soportada por omegaUp, les informaremos oportunamente.

¡Mi mami dice que cin/cout es malo y no debo juntarme con ellos!

Si no me equivoco, durante mucho tiempo se ha tratado a scanf y printf como el pan de cada día para la entrada y salida en los concursos de programación, al menos en México. Mientras tanto, se satanizó a cin y cout por ser lentos (o especiales, como dice mi mami) para realizar entrada y salida eficiente.

Sin embargo esto siempre fue un mito, los métodos cin/cout son incluso más eficientes que scanf/printf, solo había que descubrir el por que no lo notamos.

Resulta que cin/cout son muy buenos amigos de scanf/printf. Como son tan buenos amigos, al realizar la lectura y salida no querían alejarse demasiado, por lo que cin/cout tenía que sincronizarse para estar siempre a la par de scanf/printf.

Para no hacer el cuento largo, hay una forma de desactivar la opción de sincronización entre cin/cout y scanf/printf, solo es necesario incluir al inicio del main:

cin.tie(0);
ios_base::sync_with_stdio(0);

Con esto podemos usar cin y cout sin temor a obtener TLE por lectura lenta, ¡Yaaay!

¿Y eso es todo? ¿Ya puedo disfrutar de cin y cout?

Casi. Antes de cantar victoria hay un último detalle para evitar los TLE. Gracias a un último experimento, encontramos que cuando se presentaban outputs muy grandes, cin/cout optimizado seguía lanzando TLE cuando scanf/printf no.

¡Tranquilos! También es posible evitar este error. El problema se presentaba porque comúnmente usaríamos lo siguiente: cout << numero << endl. Sucede que endl, además de imprimir un salto de línea, hace flush en el flujo de salida, lo cual es considerablemente costoso al imprimir muchas líneas y entorpece el rendimiento.

Para que la salida sea eficiente, recomendamos que uses el salto de línea literal "\n".

Con los dos trucos anteriores, la eficiencia de cin/cout mejora generalmente un 5-10% los resultados obtenidos por scanf/printf. Bastante cool, ¿no?

Aunque el objetivo original no es ganar unas cuantas centésimas de segundo en eficiencia, sino dar la oportunidad a aquellos olímpicos que no manejan scanf/printf para seguir usando cin/cout sin enfrentarse a más complicaciones.

Finalmente les dejó un ejemplo de cómo usar todo lo anterior en un código de C++. Espero que algo de esto les pueda ayudar en el futuro. Les deseo lo mejor 🙂

#include <bits/stdc++.h>
#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

int main(){
        optimizar_io

        int a, b;
        cin >> a >> b;
        cout << a + b << "\n";

        return 0;
}

El camino rumbo a la IOI 2014

Después de varios meses de preparación y selección, México está listo para participar en la IOI 2014 a celebrarse en Taiwán del 13 al 20 de Julio.

De izquierda a derecha, nuestros seleccionados son:

  1. Carlos Galeana Hernández del Distrito Federal
  2. Daniel Talamás Cano de Coahuila
  3. Diego Alonso Roque Montoya de Nuevo León
  4. Jordán Alexander Salas de Coahuila

Nuevamente, nuestra selección cuenta con 3 ganadores absolutos de la Olimpiada Mexicana de Informática: Jordán ganó la OMI 2014, Talamás ganó la OMI 2013 y Diego Roque ganó la OMI 2012. Les deseamos la mejor de las suertes!

Todos los concursos de selección y la gran mayoría de las prácticas usadas durante el proceso están disponibles en omegaUp. Estos fueron los concursos y problemas usados:

Etapa 1
Durante esta etapa le pedimos a los olímpicos que lean el libro de Problemas y Algoritmos de Luis Vargas como mínimo como guía para resolver los problemas.

Temas introductorios: variables, cadenas, arreglos, matrices, ciclos, mcd, mcm:
Pilas, colas y búsqueda binaria
Búsquedas, árboles y acotamiento y poda
Recursión y backtracking
Búsquedas con espacios de estados
Divide y vencerás
Programación dinámica
Teoría de Grafos
Etapa 2 
 Esta etapa consistió de entrenamientos presenciales y prácticas externas.
Etapa 3

Material de lectura

Como parte del proceso, recomendamos a nuestros olímpicos revisar a profundidad los siguientes sitios con material de estudio y problemas para practicar:

  1. Temario oficial para la IOI.
  2. El libro en español de Luis Vargas sobre Problemas y Algoritmos. Básicamente el objetivo de la Etapa 1 es que dominen los contenidos de este libro, por lo que su lectura (y práctica) es casi obligatoria. Les recomendamos no esperar a que inicie el preselectivo para empezar a leerlo.
  3. Libros recomendados para la IOI, a estas alturas su lectura es casi obligadasi desean llegar y tener buenos resultados en la IOI:
    1. Introduction to Algorithms 3rd Edition, Cormen et. al.
    2. Competitive Programming 1, 2 y 3, Steven & Felix Halim. La versión electrónica del Libro 1 ya es gratis.
    3. Otro libro introductorio: Algorithms Unlocked de Cormen. Más prosa y menos profundidad en las demostraciones que el Introduction al Algoritmos. Recomendado para quienes están en su primer año de concursos.
  4. omegaUp 🙂
  5. El blog de Pier Paolo, sección Algoritmos: http://pier.guillen.com.mx/
  6. El blog de Rodrigo Burgos: http://algorithmmx.blogspot.com/
  7. Topcoder Contenido educacional (altamente recomendado!)
  8. Preguntas omegaUp –  Cualquier duda técnica que tengan, la pueden publica en nuestro sitio de preguntas. También pueden leer nuestras respuestas a preguntas pasadas.
  9. Guía rápida para el ACM ICPC. Muy buena para repasar pero no todos los temas aplican para la IOI, chequen el temario primero.

Otros sitios para practicar

  1. Croatian Open Competition in Informatics (COCI). Varios meses antes de la IOI, el comité de la Olimpiada de Croacia hace exámenes en línea. Los exámenes son de muy buen nivel y todos los problemas con sus soluciones están publicados en la misma página, les recomendamos darles un vistazo y practicar con todos ellos. Noten que los problemas de la COCI están en inglés y no son traducidos al español, por lo que es bueno que estén preparados. Afortunadamente Google Translate típicamente hace un buen trabajo con estos enunciados.
  2. USA Computing Olympiad (USACO)   Estos problemas sí son traducidos al español. Otro detalle importante sobre la USACO/COCI es que sus futuros competidores en la IOI también participan en estos concursos, por lo que les servirá para medir su nivel.
  3. USACO Training Gate. Plataforma paso-a-paso para entrenar con problemas para la IOI. Incluye muy buenas explicaciones de la construcción de soluciones a varios problemas y tutoriales. Este blog tiene varias soluciones para el USACO training gate. Úsenlas sólo cuando estén completamente atorados en un problema, después de haberlo intentado.
  4. Topcoder.com/tc
  5. Codeforces: http://codeforces.com/
  6. ACM UVa Online Judge
  7. Codechef: http://www.codechef.com/

Esperamos que esta información le sirva a las próximas generaciones que participarán por un lugar en la Selección Mexicana de Informática.

Yeah, science b#$ch!: Entre más omegaUp, mejores resultados

Del 1 al 6 de Mayo pasados, se llevó a cabo la Olimpiada Mexicana de Informática 2014 en Pachuca, Hidalgo. Más de 100 participantes de toda la república concursaron y omegaUp fue la plataforma de evaluación oficial (el examen del Día 1 lo puedes encontrar aquí y el de el Día 2 aquí).

Por primera vez, durante el periodo 2013-2014 varios Estados, como Morelos, Chihuahua y Guanajuato  empezaron a promover omegaUp entre sus olímpicos y usar nuestra plataforma para correr sus concursos locales estatales.

Dentro de los resultados, la estadística que más nos llamó la atención en omegaUp fue la tabla de posiciones por Estado. Minutos antes de la OMI 2014, ya habíamos predicho el Top 10 de Estados basados en las visitas a omegaUp.com durante los 6 meses anteriores a la OMI:

 

Los resultados finales por Estado fueron:

Si bien, el orden no es exactamente el mismo, 9 de los 10 mejores Estados en la OMI también estuvieron dentro del Top 10 de visitas a omegaUp.com. Entendemos que usar más omegaUp no es el único factor para tener buenos resultados en la OMI, pero esta estadística es una buena muestra de que omegaUp funciona!

Recomendamos a todos los Estados promover omegaUp entre sus alumnos y usarlo para correr sus concursos locales. Entre más temprano en el proceso lo usen, será mejor – tendrán más visitas y la probabilidad de tener un mejor lugar en la OMI será más alta.

Practicando para la OMI en omegaUp

Si estás practicando para la Olimpiada Mexicana de Informática 2014, omegaUp tiene disponibles los exámenes nacionales desde el 2009 para que intentes resolverlos. Aquí están los enlaces a los concursos de práctica

Nuevamente agradecemos a Kuko Lopez de la OIEG por ayudarnos a subir los problemas del 2009 al 2011.
Que se diviertan!

 

 

38 nuevos problemas de Karel disponibles gracias a la OIEG!

La Olimpiada de Informática del Estado de Guanajuato (OIEG), liderada este año por José Refugio López (Kuko), han hecho públicos 38 problemas de Karel para que la comunidad en general pueda practicar previo a la Olimpiada Mexicana de Informática 2014. 

Pueden resolver los nuevos problemas en los siguientes concursos:

Nivel introductorio:

Nivel básico

Nivel intermedio